رنگ‌آمیزی فهرستی گراف

در نظریه گراف، که شاخه‌ای از ریاضیات است، رنگ‌آمیزی لیستی نوعی از رنگ‌آمیزی گراف است. در این رنگ‌آمیزی برای هرراس لیستی از رنگ‌ها وجود دارد که آن راس می‌تواند توسط یکی از رنگ‌های این لیست رنگ شود. این شاخه ابتدا توسط ویزینگ^[۱](به انگلیسی: Vising)، اردوش(به انگلیسی: Erdős)، رابین(به انگلیسی: Rubin) و تیلور(به انگلیسی: Taylor)^[۲]^[۳]^[۴] مورد مطالعه قرار گرفت و بنیان آن بنا شد.

تعریف

G را یک گراف در نظر بگیرید و برای هر راس مانند v از گراف، (L(v را لیستی از رنگ‌های موجود برای آن رأس، تعریف کنید. رنگ‌آمیزی لیستی یک رنگ‌آمیزی انتخابی است که به هر راس مانند v یک رنگ دلخواه از لیست رنگ‌های آن راس ((L(v) متناظر می‌کند. به یک رنگ‌آمیزی لیستی خوب می‌گوییم هرگاه هیچ دو راس مجاوری همرنگ نباشند. یک گراف را k-لیست رنگ‌پذیر می‌نامیم هرگاه مستقل از این که لیست k رنگیِ رنگ‌های هر راس چیست، یک رنگ‌آمیزی لیستی خوب برای آن وجود داشته‌باشد. عدد رنگی لیستی ((ch(G) گراف G، کوچکترین عدد k است که گراف k، G رنگ‌پذیر است.

به بیان دقیق‌تری، برای یک تابع مانند f که به هر راس مانند v یک عدد صحیح مثبت، (f(v را نسبت می‌دهد، گراف G را f-لیست رنگ‌پذیر می‌نامند، هرگاه مستقل از این که لیست (f(v رنگیِ هر راس مانند v شامل چه رنگ‌هایی باشد، یک رنگ‌آمیزی لیستی خوب برای آن وجود داشته‌باشد. به‌طور خاص اگر برای هر راس مانند f(v) = k ،v باشد، گراف k-لیست رنگ‌پذیر می‌باشد.

مثال

فرض کنید q یک عدد صحیح مثبت باشد و G یک گراف کامل دوبخشی K_q,q^q باشد. رنگ‌های موجود را با q² عدد دو رقمی مختلف در مبنای q نمایش می‌دهیم. در بخشی از این گراف دو بخشی که q راس دارد، هر راس از گراف را متناظر با مجموعه‌ای از رنگ‌ها در نظر می‌گیریم که رقم باارزش آن‌ها یکسان است. برای مثال به راس شمارهٔ i ام مجموعه رنگ‌های {i0,i1, … ,iq} متناظر می‌کنیم. در بخش دیگر از این گراف دو بخشی، به هر راس از q^q راس این گراف یک مجموعه از رنگ‌ها مانند {... ,0a, 1b, 2c}، به طوری که رقم باارزش آن‌ها متفاوت باشد. به تعداد q^q تا مجموعه با چنین خاصیتی وجود دارد، زیرا تعداد q-تایی‌های (...,a,b,c) برابر با q^q است. برای مثال اگر q = 2 باشد، گراف دو بخشی K_2,4 خواهیم داشت. در این گراف دو راس واقع در یک بخش این گراف مجموعه رنگ‌های {00,01}, {10,11} و 4 راس واقع در بخش دیگر گراف مجموعه رنگ‌های {00,10}, {00,11}, {01,10}, {01,11} را دارند. تصویر روبرو یک مثال بزرگ‌تر را به ازای q = 3 نشان می‌دهد.

عدد رنگی لیستی گراف G از q کوچک‌تر یا مساوی نیست. مستقل از این که چه رنگی برای هر راس انتخاب شود، در بخش بزرگ‌تر راسی که لیست رنگی آن برابر با مجموعه رنگ‌های بخش کوچک‌تر است، نمی‌تواند رنگ شود. برای مثال اگر راس با لیست رنگی {00,01} با 01 و راس با لیست رنگی {10,11} با 10 رنگ شود، سپس راس با لیست رنگی {01,10} با هیچ‌کدام از دو رنگ 01 و 10 نمی‌تواند رنگ شود. بنابراین عدد رنگی لیستی G حداقل q + 1 است. ^[۵]

به‌طور مشابه، اگر $n={\binom {2k-1}{k}}$ ، گراف کامل دو بخشیk، K_n,n-لیست رنگ‌پذیر نیست. فرض کنید 2k-1 رنگ موجود باشد و در یک بخش از گراف هر راس با بقیه رئوس در یک k-تایی از این رنگ‌ها متفاوت باشد. پس هر بخش از گراف باید حداقل از k رنگ استفاده کند، در غیر این‌صورت، بعضی از راس‌ها، بی‌رنگ می‌مانند، اما این شرط باعث می‌شود که دو راس مجاور هم‌رنگ باشند. به‌طور خاص گراف مسئله سه روستا، 3-لیست رنگ‌پذیر و گراف کامل دوبخشی که هر بخش آن n رأس دارد ۴-لیست رنگ‌پذیر است.^[۲]

ویژگی‌ها

عدد رنگی لیستی (ch(G از قواعد زیر برای گراف G با n راس، عدد رنگی (X(G و بیشینه درجه (Δ(G :

(ch(G) ≥ χ(G. یک گراف k لیست رنگ‌پذیر، یک رنگ‌آمیزی لیستی خوب دارد، پس این گراف یک رنگ‌آمیزی معمولی با K رنگ دارد.
(ch(G معمولاً، توسط عدد رنگی محدود نمی‌شود، به عبارتی ((ch(G) ≤ f(χ(G به‌طور معمول برای هیچ تابعی مانند f برقرار نخواهد بود. به‌طور خاص، همان‌طور که مثال‌های گراف کامل دوبخشی نشان می‌دهد، گراف‌هایی وجود دارد که χ(G) = 2 ولی (ch(G تقریباً بزرگی دارند.^[۵]
(ch(G) ≤ χ(G) ln(n^[۶]^[۷]
ch(G) ≤ Δ(G) + 1. ^[۱]^[۲]
اگر G یک گراف مسطح باشد ch(G) ≤ 5. ^[۸]
اگر G یک گراف مسطح دوبخشی باشد ch(G) ≤ 3. ^[۹]

محاسبه عدد رنگی لیستی

دو مسئله الگوریتمی که مطرح شده‌است:

k-لیست رنگ‌پذیری. تصمیم می‌گیرد که گراف داده شده، به ازای k داده شده، k لیست رنگ‌پذیر است یا نه.
(j, k)-لیست رنگ‌پذیری. تصمیم می‌گیرد که گراف داده شده f-لیست رنگ‌پذیر است یا نه، به ازای یک تابع داده شده $f:V\to \{j,\dots ,k\}$

مسئلهٔ k-لیست رنگ‌پذیری در گراف‌های دوبخشی برای هر k ≥ 3 $\Pi _{2}^{p}$ -کامل است، و به‌طور مشابه برای 4-لیست رنگ‌پذیری در گراف‌های مسطح، 3-لیست رنگ‌پذیری در گراف‌های بدون مثلثی، (2, 3)-لیست رنگ‌پذیری برای گراف‌های مسطح دوبخشی.^[۳] ^[۱۰]

می‌توان در زمان خطی مشخص کرد که یک گراف 2-لیست رنگ‌پذیر است یا نه. برای این کار به‌طور مکرر راس‌های درجه صفر یا یک را حذف می‌کنیم تا جایی که به یک گراف با بیشینه درجه‌ی دو برسیم. گراف اولیه k-لیست رنگ‌پذیر است اگر و تنها اگر گراف ساده شده یک دور زوج یا یک گراف تتا باشد که از سه مسیر با نقطهٔ پایانی مشترک تشکیل شده‌باشد، که طول 2 تا از آن‌ها دو و طول سومی زوج باشد.

جستارهای وابسته

List edge-coloring

منابع

↑ ^۱٫۰ ^۱٫۱ Vizing, V. G. (1976), "Vertex colorings with given colors", Metody Diskret. Analiz. (in Russian) 29: 3–10
↑ ^۲٫۰ ^۲٫۱ ^۲٫۲ Erdős, P.; Rubin, A. L.; Taylor, H. (1979), "Choosability in graphs" بایگانی‌شده در ۹ مارس ۲۰۱۶ توسط Wayback Machine, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congressus Numerantium 26, pp. 125–157
↑ ^۳٫۰ ^۳٫۱ Gutner, Shai (1996), "The complexity of planar graph choosability", Discrete Mathematics 159 (1): 119–130, arXiv:0802.2668, doi:10.1016/0012-365X(95)00104-5
↑ Jensen, Tommy R.; Toft, Bjarne (1995), Graph coloring problems, New York: Wiley-Interscience, ISBN 0-471-02865-7
↑ ^۵٫۰ ^۵٫۱ Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics 152 (1-3): 299–302, doi:10.1016/0012-365X(95)00350-6, MR 1388650
↑ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 1 بایگانی‌شده در ۲۹ اوت ۲۰۱۷ توسط Wayback Machine", Talk, retrieved May 29, 2010
↑ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 2 بایگانی‌شده در ۳۰ اوت ۲۰۱۷ توسط Wayback Machine", Talk, retrieved May 29, 2010
↑ Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B 62: 180–181
↑ Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica 12: 125–134, doi:10.1007/BF01204715
↑ Gutner, Shai; Tarsi, Michael (2009), "Some results on (a:b)-choosability", Discrete Mathematics 309 (8): 2260–2270, doi:10.1016/j.disc.2008.04.061

[vizing-1] ۱٫۰ ^۱٫۱ Vizing, V. G. (1976), "Vertex colorings with given colors", Metody Diskret. Analiz. (in Russian) 29: 3–10

[erdos-2] ۲٫۰ ^۲٫۱ ^۲٫۲ Erdős, P.; Rubin, A. L.; Taylor, H. (1979), "Choosability in graphs" بایگانی‌شده در ۹ مارس ۲۰۱۶ توسط Wayback Machine, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congressus Numerantium 26, pp. 125–157

[gutner-3] ۳٫۰ ^۳٫۱ Gutner, Shai (1996), "The complexity of planar graph choosability", Discrete Mathematics 159 (1): 119–130, arXiv:0802.2668, doi:10.1016/0012-365X(95)00104-5

[4] Jensen, Tommy R.; Toft, Bjarne (1995), Graph coloring problems, New York: Wiley-Interscience, ISBN 0-471-02865-7

[g96-5] ۵٫۰ ^۵٫۱ Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics 152 (1-3): 299–302, doi:10.1016/0012-365X(95)00350-6, MR 1388650

[6] Eaton, Nancy (2003), "On two short proofs about list coloring - Part 1 بایگانی‌شده در ۲۹ اوت ۲۰۱۷ توسط Wayback Machine", Talk, retrieved May 29, 2010

[7] Eaton, Nancy (2003), "On two short proofs about list coloring - Part 2 بایگانی‌شده در ۳۰ اوت ۲۰۱۷ توسط Wayback Machine", Talk, retrieved May 29, 2010

[8] Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B 62: 180–181

[9] Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica 12: 125–134, doi:10.1007/BF01204715

[10] Gutner, Shai; Tarsi, Michael (2009), "Some results on (a:b)-choosability", Discrete Mathematics 309 (8): 2260–2270, doi:10.1016/j.disc.2008.04.061

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]