رنگ‌آمیزی یالی

در نظریهٔ گراف، یک رنگ‌آمیزی یالی از یک گراف، نسبت دادن "رنگ‌ها" به یال‌های گراف است به نحوی که هیچ دو یال مجاوری رنگ یکسان نداشته باشند. برای مثال، تصویر سمت چپ نمایانگر یک رنگ‌آمیزی یالی از یک گراف با رنگ‌های قرمز، آبی، و سبز است. رنگ‌آمیزی یالی یکی از انواع مختلف رنگ‌آمیزی گراف است. مسئلهٔ رنگ‌آمیزی یالی بررسی می‌کند که آیا ممکن است یال‌های یک گراف داده شده را با حداکثر $k$ رنگ متفاوت که $k$ داده شده‌است، یا با کمترین تعداد رنگ ممکن، رنگ کرد. کمترین تعداد لازم رنگ برای یال‌های یک گراف داده شده، شاخص رنگی آن گراف نامیده می‌شود. برای مثال، گراف تصویر با سه رنگ، رنگ می‌شود ولی نمی‌توان آن را با دو رنگ رنگ کرد، پس شاخص رنگی آن سه است.

یک ۳-رنگ‌آمیزی-یالی از گراف Desargues

بنابر قضیهٔ ویزینگ، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی یک گراف ساده برابر با بیشترین درجهٔ آن Δ یا Δ+۱ است. برای برخی از گراف‌ها مانند گراف‌های دوبخشی یا گراف‌های مسطح با درجهٔ بالا تعداد رنگ‌های لازم همیشه Δ است؛ ولی برای گراف‌های چندگانه تعداد رنگ‌های ممکن است به بزرگی ۳Δ/۲ باشد. الگوریتم‌هایی با زمان‌های چندجمله‌ای وجود دارند که رنگ‌آمیزی بهینهٔ گراف‌های دوبخشی یا گراف‌های غیر دوبخشی ساده که حداکثر Δ+۱ رنگ لازم دارند را محاسبه می‌کند؛ در صورتی که مسئلهٔ کلی یافتن رنگ‌آمیزی بهینه ان‌پی کامل است و سریع‌ترین الگوریتم شناخته‌شده برای آن، زمان نمایی نیاز دارد. انواع دیگری از مسئلهٔ رنگ‌آمیزی یالی مطالعه شده‌اند که در آن‌ها نسبت دادن رنگ‌ها به یال‌ها باید شرایط دیگری غیر از نامجاور بودن را نیز برآورده کند. مسئلهٔ رنگ‌آمیزی گراف کاربردهایی در مسائل زمان بندی و نیز انتساب فرکانس برای شبکه‌های فیبرنوری دارد.

مثال

گراف دوری با طول دور زوج به دو رنگ و با طول فرد به سه رنگ برای رنگ‌آمیزی یالی نیاز دارد. در این گراف‌ها، رنگ‌آمیزی یالی به صورت یک‌درمیان صورت می‌گیرد.[1]

ساختار هندسی یک ۷-رنگ‌آمیزی-یالی گراف کامل

K ۸

. هر کدام از ۷ دستهٔ رنگ یک یال از رأس مرکزی به یکی از رأس‌های چندضلعی دارد که سه یال بر آن عمود است.

در گراف کامل $K n$ با $n$ زوج به $n - ۱$ رنگ نیاز داریم. رنگ‌آمیزی گراف کامل، حالت خاص (Baranyai’s theorem]] Soifer 2008]]) به‌شمار می‌رود که راه‌حل هندسی زیر را ارائه می‌دهد: $n$ نقطه در مرکز یک $n - ۱$ -ضلعی قرار دهید. به هر یال رأس مرکزی، رنگ متفاوتی را انتساب دهید. برای یال‌های دیگر رئوس نیز همین‌کار را با رعایت شروط رنگ‌آمیزی انجام دهید. درصورتی که $n$ فرد باشد، برای رنگ‌آمیزی یالی به $n$ رنگ نیاز داریم: هر رنگ برای $(n - ۱)/۲$ یال قابل استفاده است که این تعداد یال، $۱/ n$ تعداد کل یال‌هاست.[2]

یکی از مسائل متداول در رنگ‌آمیزی یالی، رنگ‌آمیزی گراف‌های فرد است. گرافی که در آن هر رأس دقیقاً به $n$ رأس دیگر یال دارد و به صورت $O n$ نشان داده می‌شود. گراف Petersen حالتی خاص از این گراف‌هاست که در آن $n$ برابر ۳ باشد. گراف فرد با $n$ های ۳٬۴,۸ به $n$ رنگ و گراف فرد با $n$ های ۵٬۶,۷ به $n + ۱$ رنگ برای رنگ‌آمیزی نیاز دارد.[3]

مسئله پیدا کردن جدول بازی‌ها برای چندین تیم را در نظر بگیرید که در آن هر تیم می‌بایست با دیگر تیم‌ها بازی کند، هرتیم در یک روز حداکثر یک بازی انجام می‌دهد و بازی‌ها در ۶ روز هفته (به جز جمعه‌ها) می‌تواند انجام شود. این مسئله را می‌توان به صورت رنگ‌آمیزی گراف فرد با ${{{1}}}$ مدل کرد که (Biggs 1972) این مسئله را حل کرده‌است.

تعریف

رنگ‌آمیزی یالی به انتساب رنگی مناسب به هر یال گفته می‌شود به صورتی که به هیچ دو یال مجاور، رنگ یکسانی منتسب نشود. در این تعریف دو یال مجاور به دو یالی گفته می‌شود که رأس مشترک داشته باشند. رنگ‌آمیزی یالیی گراف $G$ معادل رنگ‌آمیزی رئوس گراف خطی $L (G)$ است. گراف خطی $L (G)$ گرافی است که به ازای هر یال $G$ یک رأس دارد و یال‌های آن معادل جفت یال‌های مجاور در $G$ است.

به رنگ‌آمیزی یالی با $k$ رنگ مختلف $k$ -رنگ‌آمیزی-یالی گفته می‌شود. به گرافی که این‌گونه قابل رنگ‌آمیزی باشد $k$ -رنگ‌پذیر-یالی گفته می‌شود. کمترین تعداد رنگ برای رنگ‌آمیزی یالی یک گراف را شاخص رنگی یا عدد رنگی یال گراف می‌گویند و آن را با $χ' (G)$ نشان می‌دهند. همچنین شاخص رنگی را گاهی با نماد $χ ۱ (G)$ نشان می‌دهند که اندیس ۱ نشان‌دهنده یک بُعدی بودن یال‌هاست. گرافی که که شاخص رنگی آن $k$ باشد را $k$ -شاخص-یالی می‌نامند. نکتهٔ قابل توجه در اینجا این است که شاخص رنگی با عدد رنگی متفاوت است. عدد رنگی کمترین تعداد رنگ‌ها برای رنگ‌آمیزی رئوس گراف است و با $χ(G)$ یا $χ ۰ (G)$ نشان داده می‌شود.

در صورتی که ذکر نشود همه گراف‌ها را گراف ساده فرض می‌کنیم. در مقابل گراف ساده، گراف‌های چندگانه تعریف می‌شود که گرافی است که یال‌ها بتوانند ابتدا و انتهای یکسانی داشته باشند یعنی بین دو رأس چندین یال وجود داشته باشد یا گراف طوقه داشته باشد. در بسیاری از مسائل رنگ‌آمیزی یالی، الگوریتم‌ها برای گراف ساده و گراف چندگانه متفاوت خواهد بود و برای تبدیل راه‌حل‌های رنگ‌آمیزی گراف ساده به گراف چندگانه ملاحظات بسیاری مورد نیاز است.

رابطه با تطابق

این گراف مسطح ۳-منتظم ۱۶ رأس و ۲۴ یال دارد، ولی در هر تطابق بیشینه فقط ۷ یال دارد. بنابراین برای هر رنگ‌آمیزی یالی آن به چهار رنگ نیاز است.

یک تطابق در گراف $G$ مجموعه‌ای از یال‌های نامجاور است؛ یک تطابق کامل یک تطابق است که یال‌های آن تمامی رأس‌ها را پوشش داده باشند، و تطابق بیشینه تطابقی است که بیشینه یال‌های ممکن را داراست. در رنگ‌آمیزی یالی، مجموعه یال‌های دارای یک رنگ خاص باید نامجاور باشند پس تشکیل یک تطابق می‌دهند. بنابراین یک رنگ‌آمیزی درست، معادل افراز کردن گراف به تطابق‌های جدا از هم است.

اگر اندازهٔ تطابق بیشینهٔ یک گراف کوچک باشد، آن‌گاه تعداد تطابق‌های لازم برای پوشاندن تمام یال‌های گراف زیاد است. به بیان رسمی‌تر، اگر یک گراف دارای $m$ یال باشد و حداکثر $β$ یال متعلق به یک تطابق بیشینه باشند، آن‌گاه هر رنگ‌آمیزی یالی گراف حداقل نیاز به $m / β$ رنگ متفاوت دارد.[4] برای مثال، گراف ۱۶-رأسی در تصویر روبه‌رو ${{{1}}}$ یال دارد. در این گراف، تطابق کامل وجود ندارد زیرا اگر رأس وسط تطبیق داده شود، رأس‌های تطبیق داده نشده باقی‌مانده در سه مؤلفهٔ همبندی متفاوت با ۴، ۵، و ۵ رأس جای می‌گیرند و مؤلفه‌های با تعدادرأس فرد تطابق کامل نخواهند داشت. برای این گراف تطابق بیشینه‌ای با ۷ یال موجود است، پس $β = ۷$ . بنابراین، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی حداقل ۲۴/۷ خواهد بود و چون تعداد رنگ‌ها باید عدد درستی باشد، حداقل به ۴ رنگ نیاز است.

برای یک گراف منظم از درجهٔ $k$ که تطابق کامل ندارد، می‌توان از این کران پایین استفاده کرد و نشان داد حداقل $k + ۱$ رنگ نیاز است.[4] به‌طور خاص، این گفته برای گراف‌های منظم با تعداد فردی رأس (مانند گراف‌های کامل فرد) درست است؛ برای این گراف‌ها، طبق لم دست دادن (hankshaking lemma)، $k$ باید عددی زوج باشد. اما نامساوی $χ' \geq m / β$ کاملاً شاخص رنگی هر گراف منظمی را توضیح نمی‌دهد، زیرا گراف‌های منظمی وجود دارند که تطابق کامل دارند اما $k$ -رنگ‌پذیر-یالی نیستند. برای مثال، گراف پترسن منظم است با $m = ۱۵$ یال و $β = ۵$ یال در تطابق کامل، ولی ۳-رنگ‌آمیزی-یالی ندارد.

رابطه با درجه

قضیهٔ ویزینگ

عدد رنگی یالی یک گراف $k$ رابطهٔ نزدیکی با بیشینه درجهٔ آن گراف $Δ(G)$ ، بیشترین تعداد ممکن یال مجاور به هر رأسی از آن گراف، دارد. واضحاً $χ' (G) \geq Δ(G)$ زیرا اگر $Δ$ یال متفاوت همگی به یک رأس برسند، آن‌گاه همهٔ آن‌ها باید رنگی متفاوت از دیگری داشته باشند و این امر هنگامی ممکن است که حداقل $Δ$ رنگ متمایز برای نسبت دادن به آن‌ها وجود داشته باشد. قضیهٔ ویزینگ (نامیده شده به خاطر ودیم جی ویزینگ که این قضیه را در ۱۹۶۴ اثبات و منتشر کرد) بیان می‌کند که این مرز تقریباً دو طرفه است، عدد رنگی یالی یا برابر $Δ(G)$ است یا $Δ(G) + ۱$ . وقتی $χ' (G) = Δ(G)$ گراف $G$ از کلاس ۱ و در غیر این صورت از کلاس ۲ خوانده می‌شود.

تمام گراف‌های دوبخشی از کلاس ۱ هستند[5]، و تقریباً تمام گراف‌های تصادفی نیز از کلاس ۱ هستند[6]. اما به‌طور کلی مسئلهٔ تشخیص این که گرافی از کلاس ۱ هست یا نه، ان‌پی کامل است.[7]

ویزینگ (۱۹۶۵) ثابت کرد که گراف‌های مسطح با بیشینه درجهٔ حداقل هشت از کلاس ۱ هستند و حدس زد که برای گراف‌های مسطح با بیشینه درجهٔ هفت یا شش نیز درست باشد. از طرف دیگر گرافی‌های مسطحی با بیشینه درجهٔ دو تا پنج وجود دارند که از کلاس ۲ هستند. حدس گفته شده، پس از آن برای گراف‌های مسطح با بیشینه درجهٔ هفت اثبات شده‌است[8]. گراف‌های مسطح مکعبی بدون پل همگی از کلاس ۱ هستند، که این مسئله معادلی از قضیهٔ چهاررنگ است[9].

گراف‌های منتظم

۱-عامل-بندی از یک گراف $k$ -منتظم، یک افراز از یال‌های گراف به تطابق‌های کامل است، که معادل $k$ -رنگ‌آمیزی-یالی گراف است. یعنی یک گراف ۱-عامل-بندی دارد اگر و فقط اگر از کلاس ۱ باشد. در یک حالت خاص، یک ۳-رنگ‌آمیزی-یالی از از یک گراف مکعبی (۳-منتظم) گاهی رنگ آمیزی تیت نامیده می‌شود.

هر گراف منتظمی ۱-عامل-بندی ندارد، مانند گراف پترسن. در حالت کلی snarkها به گراف‌هایی گفته می‌شود که مانند گراف پترسن، ۳-منتظم و از کلاس ۲ هستند.

بنا به قضیهٔ کوئینگ (۱۹۱۶) هر گراف دو بخشی منتظم یک ۱-عامل-بندی دارد. این قضیه قبلاً به عنوان projective configurations مطرح شده بود و توسط ارنست استینیتز ثابت شد.

گراف‌های چندگانه

گراف چندگانهٔ شانون با درجهٔ شش، چندگانگی یال سه، که نیاز به نه رنگ در هر رنگ آمیزی یالی دارد.

برای گراف‌های چندگانه، که در آن‌ها ممکن است چند یال موازی دو رأس را چندبار به هم متصل کنند، نتیجه‌های مشابه به قضیهٔ ویزینگ ولی ضعیف‌تر از آن، عدد رنگی یالی گراف $χ' (G)$ را به بیشینه درجه $Δ(G)$ و چندگانگی گراف $μ(G)$ که بیشترین تعداد یال‌های موازی بین هر دو رأس از گراف را نشان می‌دهد، مربوط می‌کند. ساده‌ترین مثال برای نشان دادن این که قضیهٔ ویزینگ را نمی‌توان برای گراف‌های چندگانه تعمیم داد،گراف شانون است: گرافی چندگانه با سه رأس و سه دسته از یال‌های موازی، هر دسته به تعداد $μ(G)$ یال، که هر سه زوج از رأس‌ها را به هم متصل می‌کنند. در این مثال، $Δ(G) = ۲μ(G)$ (هر رأس به دو دسته از سه دسته یال‌های موازی متصل است) ولی عدد رنگی یالی گراف برابر $۳μ(G)$ است (در کل $۳μ(G)$ یال وجود دارد که هر دو تایی از آن‌ها مجاورند پس رنگ هر کدام از یال‌ها باید با بقیه متفاوت باشد). شانون(۱۹۴۹) در یک نتیجه که بعدها الهام‌بخش ویزینگ شد[10]، نشان داد که بدترین حالت برای هر گراف چندگانه این است که $χ' (G) \leq (۳/۲)Δ(G)$ . همچنین، برای هر گراف چندگانه $G$ ، $χ' (G) \leq Δ(G) + μ(G)$ ، نامساوی‌ای که برای گراف‌های ساده (که $μ(G) = ۱$ ) به قضیهٔ ویزینگ منجر می‌شود.

الگوریتم‌ها

از آن جا که مسئلهٔ امتحان کردن این که گرافی از کلاس ۱ هست یا نه، ان‌پی کامل است، هیچ الگوریتمی از زمان چندجمله‌ای وجود ندارد که گرافی را با تعداد رنگ‌های بهینه رنگ‌آمیزی یالی کند. با این وجود الگوریتم‌هایی طرح شده‌اند که یک یا چندی از این شرط‌ها را ندارند: بعضی فقط روی زیرمجموعه‌ای از گراف‌ها کار می‌کنند، بعضی همیشه از تعداد بهینهٔ رنگ استفاده نمی‌کنند، یا بعضی همیشه در زمان چندجمله‌ای اجرا نمی‌شوند.

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

در مورد گراف‌های دوبخشی یا برخی گرافهای مسطح با بیشینه درجهٔ $Δ$ ، تعداد رنگ‌های بهینه دقیقاً برابر است. کول، اُست و شیرا (۲۰۰۱) نشان دادند که رنگ‌آمیزی یالی بهینهٔ این گراف‌ها را با زمان تقریباً خطی $O(m log Δ)$ می‌توان پیدا کرد که $m$ تعداد یال‌ها است. الگوریتم‌های ساده‌تر اما بعضاً کندتر توسط کول و هاپکرافت(۱۹۸۲) و آلن (۲۰۰۳) ارائه شدند. الگوریتم آلن (۲۰۰۳) با منتظم کردن گراف ورودی، بدون تغییر درجه و تغییر محسوس سایز گراف، شروع می‌کند: با ادغام کردم زوج‌هایی از رأس‌ها که عضو یک بخش هستند و سپس اضافه کردن تعداد کمی رأس و یال دیگر. سپس اگر درجه فرد است، آلن یک تطابق کامل در زمان تقریباً خطی پیدا می‌کند، به آن یک رنگ نسبت می‌دهد و آن را از گراف حذف می‌کند، که در نتیجه درجه زوج می‌شود. در نهایت، آلن یک مشاهده از گابو (۱۹۷۶) اعمال می‌کند، که با انتخاب کردن متناوب زیرمجموعه‌هایی از یال‌ها در یک تور اویلری از گراف، آن را به دو زیرگراف منتظم تقسیم می‌کند، که در نتیجه مسئلهٔ رنگ‌آمیزی به دو زیرمسئله تقسیم می‌شود، و الگوریتم این دو زیرمسئله را به صورت بازگشتی حل می‌کند. زمان کل این الگوریتم از $O(m log m)$ است.

برای گراف‌های مسطح با بیشینه درجهٔ $Δ \geq ۷$ ، تعداد رنگ‌های بهینه دقیقاً $Δ$ است. با فرض $Δ \geq ۹$ می‌توان یک رنگ‌آمیزی یالی بهینه در زمان خطی پیدا کرد (کول و کوالیک ۲۰۰۸).

الگوریتم‌هایی که از تعداد رنگ بیشتر از تعداد بهینه استفاده می‌کنند

میسرا و گریس (۱۹۹۲) و گابو و همکاران (۱۹۸۵) الگوریتم‌هایی با زمان چندجمله‌ای برای رنگ کردن هر گراف با $Δ + ۱$ رنگ ارائه می‌دهند که حد بالایی قضیهٔ ویزینگ است.

برای گراف‌های چندگانه، کارلوف و شمویس(۱۹۸۷) الگوریتمی ارائه دادند که به اِلی آپفال نسبت دادند. در این الگوریتم ابتدا گراف چندگانهٔ $G$ با اضافه کردن یک رأس و متصل کردن آن به همهٔ رأس‌های فرد، گراف اویلری می‌شود، دور اویلری پیدا می‌شود، و یک جهت برای دور انتخاب می‌شود. سپس یک گراف دو بخشی $H$ که هر بخشش یک کپی از رأس‌های $G$ است درست می‌شود، و یک یال از رأس $u$ در بخش چپ به رأس $v$ در بخش راست رسم می‌شود اگر و فقط اگر دور اویلری جهت دار یک یال از $u$ به $v$ در $G$ داشته باشد. $H$ با یک رنگ‌آمیزی یالی برای گراف‌های دوبخشی رنگ می‌شود. هر دسته رنگ در $H$ متناظر یک دسته یال در $G$ می‌شود که بیشینه درجهٔ دو دارد؛ که یک اجتماعی از مسیرها و دورهای جدا از هم است. بنابراین به هر دسته رنگ در $H$ می‌توان سه دسته رنگ در $G$ نسبت داد. زمان این الگوریتم بستگی به زمان رنگ‌آمیزی یالی یک گراف دو بخشی دارد که با استفاده از الگوریتم کول، اُست و شیرا از $O(m log Δ)$ است. تعداد رنگ‌هایی که این الگوریتم استفاده می‌کند حداکثر $3\left\lceil {\frac {\Delta }{2}}\right\rceil$ است، که نزدیک ولی نه دقیقاً برابر حد شانون $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$ است. این الگوریتم همچنین به طریقی سرراست می‌تواند به یک الگوریتم موازی تبدیل شود. در یک مقاله، کارلوف و شمویس همچنین یک الگوریتم خطی برای رنگ کردن گراف‌های چندگانه از بیشینه درجهٔ سه با چهار رنگ ارائه می‌کنند (که با هر دو حد ویزینگ و شانون مطابقت دارد) و بر پایه‌های ساده استوار است: این الگوریتم یک رأس به گراف اضافه می‌کند تا گراف اویلری شود، یک دور اویلری پیدا می‌کند، و سپس متناوباً مجموعه‌هایی از یال‌ها را روی دور پیدا می‌کند به طوری که گراف به دو زیرگراف از بیشینه درجهٔ دو تقسیم شود. مسیرها و دورهای زوج هر زیرگراف را با دو رنگ می‌توان رنگ کرد. پس از این مرحله، هر کدام از دورهای فرد باقی‌مانده حداقل یک یال دارند که می‌توان آن را با یکی از دو رنگی که متعلق به زیرگراف دیگر است، رنگ کرد. این یال از دور فرد حذف می‌شود که در نتیجه یک مسیر باقی می‌ماند که با دو رنگ زیرگراف خود رنگ شده‌است.

یک الگوریتم حریصانه که یال‌های گراف را یکی یکی بررسی می‌کند و به هر کدام اولین رنگ موجود را نسبت می‌دهد، گاهی تا $۲Δ - ۱$ عدد رنگ مصرف می‌کند که تقریباً دو برابر تعداد رنگ‌های مورد نیاز است. اما این برتری را دارد که می‌توان از این الگوریتم در زمینهٔ الگوریتم برخط استفاده کرد که در آن گراف ورودی از قبل مشخص نیست. در این زمینه، نسبت رقابتی این الگوریتم دو است که بهینه است: هیچ الگوریتم برخط دیگری نتوانسته است عملکرد بهتری داشته باشد[11]. ولی اگر یال‌ها به ترتیبی رندم وارد شوند و گراف ورودی درجه‌ای حداقل لگاریتمی داشته باشد، آن‌گاه می‌توان به نسبت‌های رقابتی بهتری دست یافت[12].

تعدادی از مؤلفین حدس زده‌اند که بیان می‌کند که شاخص رنگی کسری هر گراف چندگانه (یک عدد که بتوان در زمان چندجمله‌ای با استفاده از برنامه‌نویسی خطی حساب کرد) یکی از شاخص‌های رنگی است[13]. اگر این حدس‌ها درست باشد، این امکان وجود دارد که عددی را بتوان محاسبه کرد که برای مورد گراف‌های چندگانه هیچ‌گاه بیشتر از یک عدد از شاخص رنگی بیشتر نباشد، که در مورد گراف‌های ساده تطابق است: تا جایی که از طریق قضیهٔ ویزینگ می‌دانیم. با این که در حالت کلی اثبات نشده‌است، ولی این حدس‌ها تا جایی می‌دانیم برای حالتی که شاخص رنگی حداقل $\Delta +{\sqrt {\Delta /2}}$ باشد درست‌اند، حالتی که برای گراف‌های چندگانه با چندگانگی به اندازهٔ کافی بزرگ رخ می‌دهد.[14]

الگوریتم‌های دقیق

به راحتی می‌توان امتحان کرد که یک گراف را با یک رنگ یا دو رنگ می‌توان رنگ‌آمیزی یالی کرد یا نه. بنابراین اولین حالت غیربدیهی رنگ‌آمیزی یالی، امتحان کردن این است که گرافی ۳-رنگ‌آمیزی-یالی می‌شود یا نه. کوالیک(۲۰۰۹) نشان داد که می‌توان در زمان $O(۱٫۳۴۴ n)$ و با استفاده از حافظهٔ خطی، امتحان کرد یک گراف ۳-رنگ‌آمیزی-یالی دارد یا نه. با این که این زمان نمایی است، ولی بسیار بهتر و سریع‌تر از امتحان کردن تمام حالت‌های ممکن نسبت دادن رنگ‌ها به یال‌هاست. هر گراف ۲-همبند ۳-منتظم با $n$ رأس، از $O(۲ n /۲)$ عدد ۳-رنگ‌آمیزی-یالی دارد، که تمام آن‌ها را می‌توان در زمان $O(۲ n /۲)$ به دست‌آورد (قدری کندتر از زمان لازم برای پیدا کردن یک رنگ‌آمیزی)؛ همانطور که گرگ کوپربرگ مشاهده کرد، گراف یک منشور بر یک $n /۲$ -ضلعی رنگ‌آمیزی‌های بسیاری دارد، که نشان می‌دهد این حد و مرز محکم است[15].

با اعمال کردن رنگ‌آمیزی رأسی به گراف خط گراف ورودی، می‌توان هر گرافی با $m$ یال را رنگ‌آمیزی یالی بهینه کرد، با زمان $2 m m O(1)$ و حافظهٔ خطی یا زمان $O(۲٫۲۴۶۱ m)$ و حافظهٔ خطی (Björklund, Husfeldt & Koivisto 2009).

از آن‌جایی که رنگ‌آمیزی یالی حتی برای سه رنگ هم ان‌پی کامل است، بعید است که وقتی که بر حسب تعداد رنگ‌ها پارامتری شود، مهارشدنی با پارامتر ثابت باشد. با این وجود، برای پارامترهای دیگری مهارشدنی هست. در عمل، زو، ناکانو و نیشیزکی(۱۹۹۶) نشان دادند که برای گراف‌هایی با عرض درختی $w$ ، یک رنگ‌آمیزی بهینهٔ یالی در زمان $O(nw (۶ w) w (w + ۱)/۲)$ قابل محاسبه است، زمانی که بر حسب $w$ فرانمایی است ولی برحسب تعداد رأس‌ها $n$ فقط خطی است.

نمهاسر و پارک(۱۹۹۱) مسئلهٔ رنگ‌آمیزی یالی را به عنوان یک برنامهٔ عدد صحیح فرمول بندی کردند و تجربهٔ خود را در استفاده از یک حل کنندهٔ برنامه‌نویسی عدد صحیح برای رنگ‌آمیزی یالی گراف‌ها توضیح دادند. ولی آن‌ها هیچ بررسی پیچیدگی زمان و حافظه‌ای برای الگوریتمشان ارائه ندادند.

خصوصیات دیگر

گراف تعمیم‌یافتهٔ پترسن

G (۹٬۲)

که به صورت یکتا ۳-رنگ‌پذیر است. یال‌های یکی از سه دسته رنگ به صورت کمرنگ نشان داده شده‌اند. دو دسته یال با رنگ‌های دیگر یا از چرخش ۴۰ درجه‌ای یال‌های کمرنگ به دست می‌آیند یا می‌توان یال‌های دور همیلتونی که با رنگ تیره نشان داده شده‌اند را یکی در میان رنگ کرد.

یک گراف به صورت یکتا $k$ -رنگ‌پذیر-یالی است اگر بدون درنظرگرفتن جایگشت رنگ‌ها فقط یک راه برای تقسیم یال‌ها به $k$ کلاس رنگی وجود داشته باشد (بدون در نظر گرفتن $k!$ جایگشت رنگ‌ها). برای $k \neq ۳$ تنها گراف‌های به صورت یکتا $k$ -رنگ‌پذیر-یالی، مسیر، دور و ستاره است. برای $k = ۳$ دیگر گراف‌ها نیز ممکن است به صورت یکتا $k$ -رنگ‌پذیر-یالی باشند. اگرچه همه گراف‌های ۳-رنگ‌پذیر همواره دارای دقیقاً سه دور همیلتونی هستند اما برعکس این موضوع صادق نیست یعنی گراف‌هایی با سه دور همیلتونی وجود دارند که به صورت یکتا ۳-رنگ‌پذیر-یالی نیستند همانند گراف‌های تعمیم‌یافتهٔ پترسن $G (۶ n + ۳, ۲)$ برای $n \geq ۲$ . تنها گراف غیر مسطح ۳-رنگ‌پذیر-یالی $G (۹٬۲)$ است و فرضیه‌ای وجود دارد که گرافی دیگر وجود ندارد[16].

یک طرح از گراف K_۳٬۳ که سه دسته یال با رنگ‌های یکسان آن، به صورت خط‌های موازی نشان داده می‌شوند.

(Folkman & Fulkerson 1969) دنباله غیر افزایشی $m ۱, m ۲, m ۳, ...$ ها از اعداد را بررسی کردند با این خصوصیت که یک رنگ‌آمیزی یالی مناسب از گراف $G$ وجود دارد که در آن گراف $m i$ یال با رنگ $i$ -ام وجود دارد. آن‌ها مشاهده کردند که اگر دنبالهٔ $P$ امکان‌پذیر باشد و در lexicographic order بزرگتر از دنبالهٔ $Q$ با همان جمع باشد، دنباله $Q$ نیز امکان‌پذیر است. اگر در lexicographic order داشته باشیم $P > Q$ ، دنباله $P$ با تعدادی متناهی از مراحل می‌تواند به $Q$ تبدیل شود. دراین مراحل از هریک از اعداد $m i$ یکی کاسته می‌شود و به $m j$ که $i < j$ یکی افزوده می‌شود. به بیان رنگ‌آمیزی یالی، از رنگی شروع می‌کنیم که توسط $P$ منتشر شده‌است. درهریک از مراحل رنگ‌های $i$ و $j$ در چرخه Kempe جابه‌جا می‌شوند. به‌طور مشخص هرگراف یک رنگ‌آمیزی یالی equitable دارد که در آن تعداد رنگ‌ها بهینه است و تعداد یال‌های هردورنگ متفاوت فقط یکی اختلاف داشته باشد.

قضیۀ De Bruijn Erdos خصوصیات رنگ‌آمیزی گراف‌های متناهی به گراف‌های نامتناهی نیز منتقل می‌شود. برای مثال قضیه‌های شانون و ویزینگ که مربوط به درجه گراف و chromatic index هستند را می‌توان به گراف‌های نامتناهی تعمیم داد[17].

(Richer 2011) مسئله پیدا کردن رسم گراف را برای گراف مکعبی با این خصوصیت که همه یال‌های رسم شده دارای یکی از سه slop متفاوت باشد و هیچ دویالی بر روی یک خط نباشند. اگر رسمی از $K ۳٬۳$ وجود داشته باشد، slopها می‌تواند به عنوان رنگ‌ها در گراف ۳-رنگ‌پذیر استفاده شود. همانطور که Richer نشان می‌دهد گراف دو بخشی ۳-منتظم با رنگ‌آمیزی تایت داده شده را می‌توان اینگونه رنگ کرد اگروتنهااگر گراف ۳-همبند باشد. برای گراف غیرچندبخشی، شرایط کمی پیچیده‌تر است: یک رنگ‌آمیزی داده شده را می‌توان با رسم گراف نشان داد اگر bipartite double cover گراف ۳-همبند باشد و درصورتی که هریک از جفت یال‌های monochromatic را حذف کنیم بازهم حاصل گرافی غیردوبخشی باشد. این شرایط را ممکن است بتوان در زمان چندجمله‌ای بررسی کرد، اگرچه مسئله بررسی گراف ۴-رنگ‌شده‌ی-یالی ۴-منتظم با رسم ۴-slop دارای پیچیدگی زمانی NP-complete است.

همان‌گونه که شاخص رنگی به بیشترین درجه و بیشترین تعداد تطابق‌های گراف مرتبط است، به linear arboricity گراف G نیز مرتبط است که آن‌را با $la(G)$ نشان می‌دهد کمترین تعداد جنگل‌های خطی است که یال‌های گراف قابل افراز به آن جنگل‌ها باشند. یک تطابق حالت خاصی از جنگل خطی است و هر جنگل خطی، ۲-رنگ‌پذیر است. بنابراین برای هر گراف G داریم: $la(G) \leq χ' (G) \leq ۲ la(G)$ . فرضیه Akiyama بیان می‌کند که $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil$ و این باید از رابطهٔ $2 la(G) - ۲ \leq χ' (G) \leq ۲ la(G)$ تبعیت کند. برای گراف با حداکثر درجه سه، $la(G)$ همیشه مقدار دو می‌گیرد و بنابراین داریم $χ' (G) \leq ۲ la(G)$ که این همان حد قضیهٔ ویزینگ است[18].

انواع دیگر رنگ‌آمیزی یالی

یک افراز گراف کامل دو بخشی K_۴٬۴ به سه جنگل، که نشان می‌دهد arboricity آن سه است.

عدد تو، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی به این شرط است که در هر مسیر با طول زوج، دنبالهٔ رنگی نیمهٔ اول مسیر و نیمهٔ دوم آن متفاوت باشد. Arboricity یک گراف، کمترین تعداد رنگ لازم برای رنگ‌آمیزی است با این شرط که به جای اینکه هیچ دو یال مجاوری همرنگ نباشد، هیچ دو یالی که در یک دور قرار دارند همرنگ نباشند. این عدد بیانگر کمینه تعداد تقسیم‌بندی گراف به جنگل است[19]. برخلاف شاخص رنگی، مقدار Arboricity را می‌توان در زمان چندجمله‌ای محاسبه کرد.[20]

رنگ‌آمیزی یالی لیستی، مسئله‌ایست که در آن گرافی داده شده‌است که در آن هر رأس، لیستی از رنگ‌ها را نگه می‌دارد و هدف پیدا کردن رنگ‌آمیزی یالی است بطوری که هر رأس با یکی از رنگ‌های لیست خودش رنگ شود. شاخص رنگی لیستی یک گراف، کوچکترین عددی مانند $k$ است بطوریکه اگر لیست رنگ‌ها حداقل $k$ رنگ داشته باشد، نحوه انتخاب رنگ از آن لیست فرقی نکند و درهرصورت رنگ‌آمیزی امکان‌پذیر باشد. بنابراین شاخص رنگی لیستی همواره از شاخص رنگی ناکوچکتر است.Dinitz conjecture در تکمیل مربع لاتین، شاخص رنگی لیستی در گراف‌های کامل دوبخشی را برابر با شاخص رنگی تعریف می‌کند. Galvin این فرضیه را به‌طور عمومی اثبات می‌کند: در هر گراف دو بخشی، مقادیر شاخص رنگی لیستی و شاخص رنگی با هم برابر است. این مسئله برای هر گراف دوبخشی دلخواه بدون دور کماکان بدون اثبات باقی‌مانده است.

تعداد زیادی از مسائل رنگ‌آمیزی رئوس قابل گسترش به رنگ‌آمیزی یالی است. برای مثال رنگ‌آمیزی یالی کامل نوع یالی از رنگ‌آمیزی کامل (نوعی رنگ‌آمیزی گراف که در آن هر جفت رنگ به حداقل یک جفت راس مجاور نسبت داده می‌شود و هدف بیشینه کردن تعداد تمام رنگ‌هاست) است[21]. رنگ‌آمیزی قوی یالی گراف نوع یالی از رنگ‌آمیزی قوی است که در آن به هر دو یالی که به یک رأس ختم می‌شوند باید رنگ‌های متفاوتی نسبت داده شود[22]. رنگ‌آمیزی قوی یالی در زمینه‌هایی همچون تخصیص شمای کانال در شبکه‌های بی‌سیم کاربرد دارد[23]. رنگ‌آمیزی بدون دور یالی یکی از انواع رنگ‌آمیزی بدون دور است که در آن هردو کلاس رنگی، یک زیرگراف بدون دور را تشکیل می‌دهد (که یک جنگل است)[24].

(Eppstein 2008) دربارهٔ رنگ‌آمیزی یالی سه‌گانه برای گراف‌های مکعبی با خصوصیات اضافی مطالعه کرد. در این رنگ‌آمیزی هیچ دو دور bichromaticی که بیش از یک یال مشترک دارند، وجود ندارد. وی نشان داد که وجود رنگ برای این مسئله معادل رسم گراف در محیط سه بعدی شطرنجی است که در آن یال‌های موازی معادل محورهای هم پایه و پایه‌های موازی شامل حداکثر دو یال می‌شود. البته ذکر این نکته ضروری است که حل این مسئله نیز مانند حل مسئله استاندارد رنگ‌آمیزی سه‌گانه NP-complete است.

رنگ‌آمیزی تام، شکلی از رنگ‌آمیزی است که از ترکیب رنگ‌آمیزی یالی و رأسی به وجود آمده است و باید همه راس‌ها و یال‌ها رنگ شوند. هر زوج رأس و یال مجاور یا دویال مجاور و همچنین هر دو رأس مجاور باید رنگ‌های متفاوتی داشته باشند. فرضیه‌ای اثبات نشده از ترکیب قضیهٔ ویزینگ و brooks به وجود می‌آید که می‌گوید برای هر گراف، تعداد رنگ‌های لازم برای رنگ‌آمیزی تام برابر بیشترین درجه گراف به‌اضافه دو است.

اگر گراف ۳-منتظم روی یک سطح با سه رنگ قابل رنگ‌آمیزی باشد، گراف مکمل آن که سطح را به مثلث‌های هم‌مساحت افراز می‌کند نیز قابل رنگ‌آمیزی یالی است (هرچند در حالت کلی، ممکن است رنگ‌آمیزی نادرست یالی باشد). رنگ‌آمیزی بدین صورت انجام می‌گیرد که هر مثلث یک یال از هر رنگ را دارد. دیگر رنگ‌آمیزی‌ها و چرخش‌های مثلث‌ها با محدودیت‌ها خاص بر روی چگونگی مرتب‌شدن رنگ‌های رئوس، می‌تواند برای کد کردن انواع مختلف اشکال هندسی به کار برده شود. برای مثال تقسیم مستطیلی (تقسیم به مستطیل‌های کوچکتر بطوری که هر سه مستطیل کنار هم در یک رأس مشترک باشند) را می‌توان درقالب برچسب‌گذاری منظم به صورت رنگ‌آمیزی دوتایی یال‌های مستطیل مکمل تعریف کرد با این محدودیت که هر یال در برخورد با هر رأس، چهار زیرمجموعهٔ پیوسته را ایجاد می‌کند که در آن‌ها رنگ‌آمیزی‌ها یکسان است. این برچسب‌گذاری، مکمل رنگ‌آمیزی مستطیلی است که در آن هر یال عمودی یک رنگ و هریال افقی نیز رنگ دیگری دارد. برای هریک از این سه نوع برچست‌گذاری منظم، مجموعه‌ای از گراف‌های برچسب‌گذاری شده یک شبکه توزیع شده را تشکیل می‌دهند که برای لیست کردن سریع ساختارهای هندسی براساس همان گراف یا پیدا کردن محدودیت‌های بیشتر به کار می‌رود[25].

یک deterministic finite automaton به عنوان یک گراف مستقیم تفسیر می‌شود که در آن هر رأس درجهٔ خروجی d را دارد و یال‌ها d-رنگ‌پذیرند بطوری که یال‌ها با رأس مبدأ مشترک، رنگ‌ها متفاوتی دارند. مسئلهٔ رنگ‌آمیزی جاده‌ها، مسئلهٔ رنگ‌آمیزی یالی گراف مستقیم است که automatonهای را نتیجه می‌دهد که synchronizing word دارند. (Trahtman 2009) این مسئله را با اثبات این مطلب که اگر گراف قویاً همبند و نامتناوب باشد چنین رنگ‌آمیزی وجود دارد، حل کرده‌است.

تئوری Ramsey به مسئلهٔ رنگ‌آمیزی $k$ -تایی گراف کامل $K n$ مربوط می‌شود که از ساختن زیرگراف کامل $K s$ از سایز داده شدهٔ $s$ که monochromatic باشد جلوگیری می‌کند. بر اساس این تئوری عددی مانند $R k (s)$ وجود دارد که هرگاه $n \geq R (s)$ رنگ‌آمیزی امکان‌پذیر نخواهد بود. برای مثال در گراف $K ۶$ با $R ۲ (۳) = ۶$ اگر یال‌ها ۲-رنگ‌شده باشد، حتماً مستطیل monochromatic وجود دارد.

کاربردها

برای زمان‌بندی مسابقات گردشی می‌توان رنگ‌آمیزی یالی یک گراف کامل را به کار برد. بدین صورت می‌توان در کمترین تعداد گردش این مسابقات را زمان‌بندی کرد بطوری که همه تیم‌ها در هر گردش بازی کنند. در این مسئله تیم‌ها به صورت رئوس و بازی‌ها به صورت یال مدل می‌شوند. بنابراین تعداد گردش‌ها برابراست با تعداد رنگ‌های مورد استفاده برای رنگ‌آمیزی یالی[26].

برای زمان‌بندی مسابقاتی که همهٔ تیم‌ها با یکدیگر بازی نمی‌کند نیز می‌توان از تکنیک‌های دیگر رنگ‌آمیزی یالی استفاده کرد. برای مثال در لیگ جهانی فوتبال، جفت تیم‌هایی که باید در طول یک سال با هم بازی کنند، براساس نتایج سالیان قبلی تعیین می‌شود. زمان‌بندی بازی‌ها از اجرای الگوریتم رنگ‌آمیزی یالی بر روی گرافی به دست می‌آید که از جفت تیم‌ها ساخته شده‌است.[27]. برای این کاربرد، قضیهٔ ویزینگ بیان می‌کند که مستقل از این که جفت تیم‌ها چگونه انتخاب شده باشند (به شرط این که هیچ دو تیمی در یک فصل دو بار با هم بازی نکنند)، همواره می‌توان زمان‌بندی‌ای استفاده کرد که حداکثر یک هفته بیشتر از تعداد تیم‌ها طول بکشد.

زمان‌بندی Open Shop یک مسئلهٔ زمان‌بندی فرایندهای تولید است. در این مسئله، مجموعه‌ای از محصولات باید تولید شوند و هر محصول برای تولید نیازمند اجرای مجموعه‌ای از وظایف است. هر وظیفه باید روی ماشین‌های خاصی اجرا شود و زمان‌بندی باید به صورتی انجام شود که وظایف به یک ماشین به‌طور همزمان نیاز نداشته باشند. اگر همه وظایف طول یکسانی داشته باشند، در این صورت مسئله به رنگ‌آمیزی گراف دوبخشی‌ای مدل می‌شود که رئوس در یک بخش گراف نشان‌دهندهٔ محصولات و رئوس بخش دیگر نشان‌دهنده ماشین‌ها هستند و یال‌ها نشان‌دهندهٔ وظایف هستند. بنابراین تعداد رنگ‌ها نشان‌دهندهٔ تعداد گام‌های زمانی برای اجرای وظایف هستند. از آن جایی که رنگ‌آمیزی گراف‌های دو بخشی در زمان چندجمله‌ای قابل انجام است، این مسئله نیز در زمان چندجمله‌ای قابل حل است[28].

(Gandham, Dawande & Prakash 2005) مسئله زمان‌بندی لینک‌ها برای پروتکل time division multiple access شبکه‌های کامپوتری بر روی شبکه‌های حسگر مطالعه کردند و راه‌حلی با رنگ‌آمیزی یالی ارائه دادند. در این مسئله باید بازه‌های زمانی برای یال‌های شبکه ارتباطی بی‌سیم انتخاب شود تا هر گره شبکه بتواند با گره‌های همسایه‌اش بدون تداخل ارتباط برقرار کند. استفاده از رنگ‌آمیزی یالی قوی (استفاده از دو بازه زمانی برای هر رنگ یال هریک برای یک جهت) مسئله را حل می‌کند ولی ممکن است تعداد بیشتری بازه زمانی مورد نیاز باشد. به جای اینکار به دنبال رنگ‌آمیزی گراف مستقیم گشتند. گراف مستقیم از دوبله کردن یال‌های غیرمستقیم شبکه تشکیل می‌شود. این گراف این خصوصیت را دارد که رنگ هر یال مستقیم $uv$ با رنگ یال‌های دیگر $v$ و همچنین رنگ یال‌های همسایه‌های $v$ متفاوت باشد. آن‌ها برای این مسئله یک الگوریتم اکتشافی براساس الگوریتم توزیع شده برای $(Δ + ۱)$ -رنگ‌آمیزی-یالی پیشنهاد دادند. در این الگوریتم پس پردازشی برای زمان‌بندی دوباره یال‌های متداخل تعبیه شده‌است.

در ارتباطات فیبر نوری، رنگ‌آمیزی مسیر مسئله‌ایست که رنگ‌ها به جفت رئوسی که با هم ارتباط دارند، اختصاص می‌یابد. مسیرها در فیبرنوری ارتباطات شبکه را برای هر رأس را نشان می‌دهد. محدودیت این است که هیچ دو مسیری که قسمت مشترکی از فیبر را تسهیم می‌کنند از فرکانس یکسانی استفاده نکنند. مسیرها می‌توانند از سوئیچ ارتباطی یکسانی عبور کنند ولی از قسمت مشترکی از فیبر با فرکانس یکسان نمی‌توانند عبور کنند. وقتی توپولوژی شبکه به صورت ستاره‌ای باشد بدین صورت که سوئیچ در مرکز قرار دارد و هر گره با فیبرنوری جداگانه‌ای به سوئیچ متصل شده‌است، مسئلهٔ رنگ‌آمیزی مسیر تبدیل به رنگ‌آمیزی یالی گراف یا گراف چندگانه می‌شود. در این حالت گره‌ها همان رئوس گراف هستند و جفت گره‌هایی که با هم ارتباط برقرار می‌کنند، یال‌ها خواهند بود. تعداد رنگ‌های به کار رفته در رنگ‌آمیزی یالی، تعداد فرکانس‌های مورد استفاده در ارتباطات بین جفت گره‌هاست. برای ارتباطات شبکه‌ای با توپولوژی درختی، راه‌حل رنگ‌آمیزی مسیر برای شبکه‌های محلی حول هر سوئیچ به‌کاربرده می‌شود و از تجمیع این راه‌حل‌ها با یکدیگر مسئله نهایی حل خواهد شد[29].

مسائل باز

جنسن و تافت(۱۹۹۵) لیستی از ۲۳ مسئلهٔ بار در رابطه با رنگ‌آمیزی یالی ارائه دادند. این لیست عبارت است از:

حدس گلدبرگ(۱۹۷۳) که شاخص رنگی و شاخص کسری داخل یک‌دیگر هستند، که اجازهٔ تخمین زدن شاخص رنگی درون یک رنگ در زمان چندجمله‌ای را نمی‌دهد.
چندین حدس از جیکوبسن و دیگران در ساختن گراف‌های بحرانی برای رنگ‌آمیزی یالی، گراف‌هایی از کلاس ۲ که هر زیرگرافی از آن‌ها یا بیشینه درجهٔ کمتر دارد یا از کلاس ۱ است. جیکوبسن در اصل حدس زد که تمامی گراف‌های بحرانی تعداد رأس‌هایشان فرد است، ولی این حدس بعدها به مرور رد شد. بسیاری از حدس‌های دیگری که این حدس را ضعیف می‌کنند، یا حد گذاشتن روی تعداد رأس‌های گراف‌های بحرانی و گراف‌های چندگانهٔ بحرانی، باز باقی‌مانده‌اند.
مسئلهٔ ویزینگ که مسئلهٔ دسته‌بندی بیشینه درجاتی است که برای گراف‌های مسطح کلاس ۲ ممکن هستند.
حدس زیرگراف کاملاً پر از ای. جی. دبلیو. هیلتون، بیانگر این که گراف‌هایی با درجهٔ حداقل $n /۳$ یا از کلاس ۱ هستند یا دارای زیرگرافی با بیشینه درجهٔ $Δ$ برابر با گراف اصلی و تعداد فرد $k$ رأس هستند، که تعداد یال‌های این زیرگراف بیشتر از $Δ (k - ۱)/۲$ است، و حدسی مشابه این حدس از Herbert Grötzsch و پاول سیمور در رابطه با گراف‌های مسطح به جای گراف‌هایی با درجهٔ زیاد.
حدسی از چتویند و هیلتون (که احتمالاً به کار گابریل آندرو دیراک برمی‌گردد) که گراف‌های منتظم با تعداد زوج $n$ رأس و درجهٔ حداقل $n /۲$ از کلاس ۱ هستند.
حدسی از کلاد برگ و دی. آر. فالکرسن که گراف‌های چندگانهٔ ۶-منتظم که از دوتا کردن هر یال یک گراف سادهٔ ۳-منتظم بدون پل به دست آمده است، ممکن است با ۶ رنگ رنگ‌آمیزی یالی شوند.
حدسی از فیورینی و ویلسون که هر گراف مسطح بدون مثلث، به جز پنجهٔ K_۱٬۳ به‌طور یکتا ۳-رنگ‌پذیر نیست.

یک حدس اخیر این است که اگر $G$ گراف چندگانهٔ $d$ -منتظم مسطح باشد، آن‌گاه $d$ ، $G$ -رنگ‌پذیر است اگر و فقط اگر $G$ ، $d$ -همبند یالی باشد. این قضیه می‌تواند به عنوان تعمیمی از قضیهٔ چهاررنگ باشد که $d$ =۳. ماریا چادنوسکی، کاترین ادواردز و پاول سیمور ثابت کردند که یک گراف چندگانهٔ ۸-منتظم یک عدد رنگی یالی ۸ دارد[30].

منابع

Soifer (2008), problem 16.4, p. 133.
Soifer (2008), problem 16.5, p. 133. The fact that either $n$ or $(n - 1)$ colors are needed is an instance of قضیه ویزینگ.
Biggs (1972); Meredith & Lloyd (1973); Biggs (1979).
Soifer (2008), p. 134.
Kőnig (1916)
Erdős & Wilson (1977).
Holyer (1981).
Sanders & Zhao (2001).
(Tait 1880); Appel & Haken (1976).
Soifer (2008), p. 136.
Bar-Noy, Motwani & Naor (1992).
Bahmani, Mehta & Motwani (2010).
Gol'dberg (1973); Andersen (1977); Seymour (1979).
Chen, Yu & Zang (2011).
Eppstein (2008).
Schwenk (1989).
Bosák (1972).
Akiyama, Exoo & Harary (1980); Habib & Péroche (1982); Horák & Niepel (1985).
Nash-Williams (1964).
Gabow & Westermann (1992).
Bosák & Nešetřil (1976).
Fouquet & Jolivet (1983); Mahdian (2002); Frieze, Krivelevich & Sudakov (2005); Cranston (2006).
Barrett et al. (2006).
Alon, Sudakov & Zaks (2002); Muthu, Narayanan & Subramanian (2007).
Eppstein (2010).
Burke, De Werra & Kingston (2004).
Skiena (2008).
Williamson et al. (1997).
Erlebach & Jansen (2001).
Maria Chudnovsky, Katherine Edwards, Paul Seymour (2012-01-13). "Edge-colouring eight-regular planar graphs". |access-date= requires |url= (help)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Soifer (2008), problem 16.4, p. 133.

[2] Soifer (2008), problem 16.5, p. 133. The fact that either $n$ or $(n - 1)$ colors are needed is an instance of قضیه ویزینگ.

[3] Biggs (1972); Meredith & Lloyd (1973); Biggs (1979).

[s134-4] Soifer (2008), p. 134.

[5] Kőnig (1916)

[6] Erdős & Wilson (1977).

[7] Holyer (1981).

[8] Sanders & Zhao (2001).

[9] (Tait 1880); Appel & Haken (1976).

[10] Soifer (2008), p. 136.

[11] Bar-Noy, Motwani & Naor (1992).

[12] Bahmani, Mehta & Motwani (2010).

[13] Gol'dberg (1973); Andersen (1977); Seymour (1979).

[14] Chen, Yu & Zang (2011).

[15] Eppstein (2008).

[16] Schwenk (1989).

[17] Bosák (1972).

[18] Akiyama, Exoo & Harary (1980); Habib & Péroche (1982); Horák & Niepel (1985).

[19] Nash-Williams (1964).

[20] Gabow & Westermann (1992).

[21] Bosák & Nešetřil (1976).

[22] Fouquet & Jolivet (1983); Mahdian (2002); Frieze, Krivelevich & Sudakov (2005); Cranston (2006).

[23] Barrett et al. (2006).

[24] Alon, Sudakov & Zaks (2002); Muthu, Narayanan & Subramanian (2007).

[25] Eppstein (2010).

[26] Burke, De Werra & Kingston (2004).

[27] Skiena (2008).

[28] Williamson et al. (1997).

[29] Erlebach & Jansen (2001).

[Edge-Colouring_Eight-Regular_Planar_Graphs-30] Maria Chudnovsky, Katherine Edwards, Paul Seymour (2012-01-13). "Edge-colouring eight-regular planar graphs". |access-date= requires |url= (help)