موضوع مقاله: رنگ‌آمیزی یالی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # رنگ‌آمیزی یالی | مقدمه: برای مثال، تصویر سمت چپ نمایانگر یک رنگ‌آمیزی یالی از یک گراف با رنگ‌های قرمز، آبی، و سبز است. | ## بخش 1: رنگ‌آمیزی یالی | مسئلهٔ رنگ‌آمیزی یالی بررسی می‌کند که آیا ممکن است یال‌های یک گراف داده شده را با حداکثر رنگ متفاوت که داده شده‌است، یا با کمترین تعداد رنگ ممکن، رنگ کرد. کمترین تعداد لازم رنگ برای یال‌های یک گراف داده شده، شاخص رنگی آن گراف نامیده می‌شود. برای مثال، گراف تصویر با سه رنگ، رنگ می‌شود ولی نمی‌توان آن را با دو رنگ رنگ کرد، پس شاخص رنگی آن سه است. بنابر قضیهٔ ویزینگ، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی یک گراف ساده برابر با بیشترین درجهٔ آن Δ یا Δ+۱ است. برای برخی از گراف‌ها مانند گراف‌های دوبخشی یا گراف‌های مسطح با درجهٔ بالا تعداد رنگ‌های لازم همیشه Δ است؛ ولی برای گراف‌های چندگانه تعداد رنگ‌های ممکن است به بزرگی ۳Δ/۲ باشد. الگوریتم‌هایی با زمان‌های چندجمله‌ای وجود دارند که رنگ‌آمیزی بهینهٔ گراف‌های دوبخشی یا گراف‌های غیر دوبخشی ساده که حداکثر Δ+۱ رنگ لازم دارند را محاسبه می‌کند؛ در صورتی که مسئلهٔ کلی یافتن رنگ‌آمیزی بهینه ان‌پی کامل است و سریع‌ترین الگوریتم شناخته‌شده برای آن، زمان نمایی نیاز دارد. انواع دیگری از مسئلهٔ رنگ‌آمیزی یالی مطالعه شده‌اند که در آن‌ها نسبت دادن رنگ‌ها به یال‌ها باید شرایط دیگری غیر از نامجاور بودن را نیز برآورده کند. مسئلهٔ رنگ‌آمیزی گراف کاربردهایی در مسائل زمان بندی و نیز انتساب فرکانس برای شبکه‌های فیبرنوری دارد. مثال گراف دوری با طول دور زوج به دو رنگ و با طول فرد به سه رنگ برای رنگ‌آمیزی یالی نیاز دارد. هر کدام از ۷ دستهٔ رنگ یک یال از رأس مرکزی به یکی از رأس‌های چندضلعی دارد که سه یال بر آن عمود است. درصورتی که فرد باشد، برای رنگ‌آمیزی یالی به رنگ نیاز داریم: هر رنگ برای یال قابل استفاده است که این تعداد یال، تعداد کل یال‌هاست., problem 16.5, p. گراف فرد با های ۳٬۴,۸ به رنگ و گراف فرد با های ۵٬۶,۷ به رنگ برای رنگ‌آمیزی نیاز دارد.; ; . مسئله پیدا کردن جدول بازی‌ها برای چندین تیم را در نظر بگیرید که در آن هر تیم می‌بایست با دیگر تیم‌ها بازی کند، هرتیم در یک روز حداکثر یک بازی انجام می‌دهد و بازی‌ها در ۶ روز هفته (به جز جمعه‌ها) می‌تواند انجام شود. این مسئله را می‌توان به صورت رنگ‌آمیزی گراف فرد با مدل کرد که (Biggs 1972) این مسئله را حل کرده‌است. تعریف رنگ‌آمیزی یالی به انتساب رنگی مناسب به هر یال گفته می‌شود به صورتی که به هیچ دو یال مجاور، رنگ یکسانی منتسب نشود. گراف خطی گرافی است که به ازای هر یال یک رأس دارد و یال‌های آن معادل جفت یال‌های مجاور در است. کمترین تعداد رنگ برای رنگ‌آمیزی یالی یک گراف را شاخص رنگی یا عدد رنگی یال گراف می‌گویند و آن را با نشان می‌دهند. همچنین شاخص رنگی را گاهی با نماد نشان می‌دهند که اندیس ۱ نشان‌دهنده یک بُعدی بودن یال‌هاست. عدد رنگی کمترین تعداد رنگ‌ها برای رنگ‌آمیزی رئوس گراف است و با یا نشان داده می‌شود. در مقابل گراف ساده، گراف‌های چندگانه تعریف می‌شود که گرافی است که یال‌ها بتوانند ابتدا و انتهای یکسانی داشته باشند یعنی بین دو رأس چندین یال وجود داشته باشد یا گراف طوقه داشته باشد. در بسیاری از مسائل رنگ‌آمیزی یالی، الگوریتم‌ها برای گراف ساده و گراف چندگانه متفاوت خواهد بود و برای تبدیل راه‌حل‌های رنگ‌آمیزی گراف ساده به گراف چندگانه ملاحظات بسیاری مورد نیاز است. یک تطابق در گراف مجموعه‌ای از یال‌های نامجاور است؛ یک تطابق کامل یک تطابق است که یال‌های آن تمامی رأس‌ها را پوشش داده باشند، و تطابق بیشینه تطابقی است که بیشینه یال‌های ممکن را داراست. در رنگ‌آمیزی یالی، مجموعه یال‌های دارای یک رنگ خاص باید نامجاور باشند پس تشکیل یک تطابق می‌دهند. اگر اندازهٔ تطابق بیشینهٔ یک گراف کوچک باشد، آن‌گاه تعداد تطابق‌های لازم برای پوشاندن تمام یال‌های گراف زیاد است. به بیان رسمی‌تر، اگر یک گراف دارای یال باشد و حداکثر یال متعلق به یک تطابق بیشینه باشند، آن‌گاه هر رنگ‌آمیزی یالی گراف حداقل نیاز به رنگ متفاوت دارد., p. در این گراف، تطابق کامل وجود ندارد زیرا اگر رأس وسط تطبیق داده شود، رأس‌های تطبیق داده نشده باقی‌مانده در سه مؤلفهٔ همبندی متفاوت با ۴، ۵، و ۵ رأس جای می‌گیرند و مؤلفه‌های با تعدادرأس فرد تطابق کامل نخواهند داشت. بنابراین، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی حداقل ۲۴/۷ خواهد بود و چون تعداد رنگ‌ها باید عدد درستی باشد، حداقل به ۴ رنگ نیاز است. برای یک گراف منظم از درجهٔ که تطابق کامل ندارد، می‌توان از این کران پایین استفاده کرد و نشان داد حداقل رنگ نیاز است. اما نامساوی کاملاً شاخص رنگی هر گراف منظمی را توضیح نمی‌دهد، زیرا گراف‌های منظمی وجود دارند که تطابق کامل دارند اما -رنگ‌پذیر-یالی نیستند. برای مثال، گراف پترسن منظم است با یال و یال در تطابق کامل، ولی ۳-رنگ‌آمیزی-یالی ندارد. رابطه با درجه قضیهٔ ویزینگ عدد رنگی یالی یک گراف رابطهٔ نزدیکی با بیشینه درجهٔ آن گراف ، بیشترین تعداد ممکن یال مجاور به هر رأسی از آن گراف، دارد. واضحاً زیرا اگر یال متفاوت همگی به یک رأس برسند، آن‌گاه همهٔ آن‌ها باید رنگی متفاوت از دیگری داشته باشند و این امر هنگامی ممکن است که حداقل رنگ متمایز برای نسبت دادن به آن‌ها وجود داشته باشد. قضیهٔ ویزینگ (نامیده شده به خاطر ودیم جی ویزینگ که این قضیه را در ۱۹۶۴ اثبات و منتشر کرد) بیان می‌کند که این مرز تقریباً دو طرفه است، عدد رنگی یالی یا برابر است یا. تمام گراف‌های دوبخشی از کلاس ۱ هستند، و تقریباً تمام گراف‌های تصادفی نیز از کلاس ۱ هستند.. ویزینگ (۱۹۶۵) ثابت کرد که گراف‌های مسطح با بیشینه درجهٔ حداقل هشت از کلاس ۱ هستند و حدس زد که برای گراف‌های مسطح با بیشینه درجهٔ هفت یا شش نیز درست باشد. از طرف دیگر گرافی‌های مسطحی با بیشینه درجهٔ دو تا پنج وجود دارند که از کلاس ۲ هستند. گراف‌های مسطح مکعبی بدون پل همگی از کلاس ۱ هستند، که این مسئله معادلی از قضیهٔ چهاررنگ است; .. گراف‌های منتظم ۱-عامل-بندی از یک گراف -منتظم، یک افراز از یال‌های گراف به تطابق‌های کامل است، که معادل -رنگ‌آمیزی-یالی گراف است. در یک حالت خاص، یک ۳-رنگ‌آمیزی-یالی از از یک گراف مکعبی (۳-منتظم) گاهی رنگ آمیزی تیت نامیده می‌شود. در حالت کلی snarkها به گراف‌هایی گفته می‌شود که مانند گراف پترسن، ۳-منتظم و از کلاس ۲ هستند. برای گراف‌های چندگانه، که در آن‌ها ممکن است چند یال موازی دو رأس را چندبار به هم متصل کنند، نتیجه‌های مشابه به قضیهٔ ویزینگ ولی ضعیف‌تر از آن، عدد رنگی یالی گراف را به بیشینه درجه و چندگانگی گراف که بیشترین تعداد یال‌های موازی بین هر دو رأس از گراف را نشان می‌دهد، مربوط می‌کند. ساده‌ترین مثال برای نشان دادن این که قضیهٔ ویزینگ را نمی‌توان برای گراف‌های چندگانه تعمیم داد،گراف شانون است: گرافی چندگانه با سه رأس و سه دسته از یال‌های موازی، هر دسته به تعداد یال، که هر سه زوج از رأس‌ها را به هم متصل می‌کنند. در این مثال، (هر رأس به دو دسته از سه دسته یال‌های موازی متصل است) ولی عدد رنگی یالی گراف برابر است (در کل یال وجود دارد که هر دو تایی از آن‌ها مجاورند پس رنگ هر کدام از یال‌ها باید با بقیه متفاوت باشد). همچنین، برای هر گراف چندگانه ، ، نامساوی‌ای که برای گراف‌های ساده (که ) به قضیهٔ ویزینگ منجر می‌شود. الگوریتم‌ها از آن جا که مسئلهٔ امتحان کردن این که گرافی از کلاس ۱ هست یا نه، ان‌پی کامل است، هیچ الگوریتمی از زمان چندجمله‌ای وجود ندارد که گرافی را با تعداد رنگ‌های بهینه رنگ‌آمیزی یالی کند. با این وجود الگوریتم‌هایی طرح شده‌اند که یک یا چندی از این شرط‌ها را ندارند: بعضی فقط روی زیرمجموعه‌ای از گراف‌ها کار می‌کنند، بعضی همیشه از تعداد بهینهٔ رنگ استفاده نمی‌کنند، یا بعضی همیشه در زمان چندجمله‌ای اجرا نمی‌شوند. رنگ‌آمیزی بهینهٔ دسته‌هایی از گراف‌ها در مورد گراف‌های دوبخشی یا برخی گرافهای مسطح با بیشینه درجهٔ ، تعداد رنگ‌های بهینه دقیقاً برابر است. | ## بخش 2: رنگ‌آمیزی یالی | کول، اُست و شیرا (۲۰۰۱) نشان دادند که رنگ‌آمیزی یالی بهینهٔ این گراف‌ها را با زمان تقریباً خطی می‌توان پیدا کرد که تعداد یال‌ها است. الگوریتم‌های ساده‌تر اما بعضاً کندتر توسط کول و هاپکرافت(۱۹۸۲) و آلن (۲۰۰۳) ارائه شدند. الگوریتم آلن (۲۰۰۳) با منتظم کردن گراف ورودی، بدون تغییر درجه و تغییر محسوس سایز گراف، شروع می‌کند: با ادغام کردم زوج‌هایی از رأس‌ها که عضو یک بخش هستند و سپس اضافه کردن تعداد کمی رأس و یال دیگر. سپس اگر درجه فرد است، آلن یک تطابق کامل در زمان تقریباً خطی پیدا می‌کند، به آن یک رنگ نسبت می‌دهد و آن را از گراف حذف می‌کند، که در نتیجه درجه زوج می‌شود. در نهایت، آلن یک مشاهده از گابو (۱۹۷۶) اعمال می‌کند، که با انتخاب کردن متناوب زیرمجموعه‌هایی از یال‌ها در یک تور اویلری از گراف، آن را به دو زیرگراف منتظم تقسیم می‌کند، که در نتیجه مسئلهٔ رنگ‌آمیزی به دو زیرمسئله تقسیم می‌شود، و الگوریتم این دو زیرمسئله را به صورت بازگشتی حل می‌کند. با فرض می‌توان یک رنگ‌آمیزی یالی بهینه در زمان خطی پیدا کرد (کول و کوالیک ۲۰۰۸). الگوریتم‌هایی که از تعداد رنگ بیشتر از تعداد بهینه استفاده می‌کنند میسرا و گریس (۱۹۹۲) و گابو و همکاران (۱۹۸۵) الگوریتم‌هایی با زمان چندجمله‌ای برای رنگ کردن هر گراف با رنگ ارائه می‌دهند که حد بالایی قضیهٔ ویزینگ است. برای گراف‌های چندگانه، کارلوف و شمویس(۱۹۸۷) الگوریتمی ارائه دادند که به اِلی آپفال نسبت دادند. در این الگوریتم ابتدا گراف چندگانهٔ با اضافه کردن یک رأس و متصل کردن آن به همهٔ رأس‌های فرد، گراف اویلری می‌شود، دور اویلری پیدا می‌شود، و یک جهت برای دور انتخاب می‌شود. سپس یک گراف دو بخشی که هر بخشش یک کپی از رأس‌های است درست می‌شود، و یک یال از رأس در بخش چپ به رأس در بخش راست رسم می‌شود اگر و فقط اگر دور اویلری جهت دار یک یال از به در داشته باشد. هر دسته رنگ در متناظر یک دسته یال در می‌شود که بیشینه درجهٔ دو دارد؛ که یک اجتماعی از مسیرها و دورهای جدا از هم است. زمان این الگوریتم بستگی به زمان رنگ‌آمیزی یالی یک گراف دو بخشی دارد که با استفاده از الگوریتم کول، اُست و شیرا از است. تعداد رنگ‌هایی که این الگوریتم استفاده می‌کند حداکثر است، که نزدیک ولی نه دقیقاً برابر حد شانون است. در یک مقاله، کارلوف و شمویس همچنین یک الگوریتم خطی برای رنگ کردن گراف‌های چندگانه از بیشینه درجهٔ سه با چهار رنگ ارائه می‌کنند (که با هر دو حد ویزینگ و شانون مطابقت دارد) و بر پایه‌های ساده استوار است: این الگوریتم یک رأس به گراف اضافه می‌کند تا گراف اویلری شود، یک دور اویلری پیدا می‌کند، و سپس متناوباً مجموعه‌هایی از یال‌ها را روی دور پیدا می‌کند به طوری که گراف به دو زیرگراف از بیشینه درجهٔ دو تقسیم شود. پس از این مرحله، هر کدام از دورهای فرد باقی‌مانده حداقل یک یال دارند که می‌توان آن را با یکی از دو رنگی که متعلق به زیرگراف دیگر است، رنگ کرد. این یال از دور فرد حذف می‌شود که در نتیجه یک مسیر باقی می‌ماند که با دو رنگ زیرگراف خود رنگ شده‌است. یک الگوریتم حریصانه که یال‌های گراف را یکی یکی بررسی می‌کند و به هر کدام اولین رنگ موجود را نسبت می‌دهد، گاهی تا عدد رنگ مصرف می‌کند که تقریباً دو برابر تعداد رنگ‌های مورد نیاز است. اما این برتری را دارد که می‌توان از این الگوریتم در زمینهٔ الگوریتم برخط استفاده کرد که در آن گراف ورودی از قبل مشخص نیست. در این زمینه، نسبت رقابتی این الگوریتم دو است که بهینه است: هیچ الگوریتم برخط دیگری نتوانسته است عملکرد بهتری داشته باشد.. ولی اگر یال‌ها به ترتیبی رندم وارد شوند و گراف ورودی درجه‌ای حداقل لگاریتمی داشته باشد، آن‌گاه می‌توان به نسبت‌های رقابتی بهتری دست یافت.. تعدادی از مؤلفین حدس زده‌اند که بیان می‌کند که شاخص رنگی کسری هر گراف چندگانه (یک عدد که بتوان در زمان چندجمله‌ای با استفاده از برنامه‌نویسی خطی حساب کرد) یکی از شاخص‌های رنگی است; ; .. اگر این حدس‌ها درست باشد، این امکان وجود دارد که عددی را بتوان محاسبه کرد که برای مورد گراف‌های چندگانه هیچ‌گاه بیشتر از یک عدد از شاخص رنگی بیشتر نباشد، که در مورد گراف‌های ساده تطابق است: تا جایی که از طریق قضیهٔ ویزینگ می‌دانیم. با این که در حالت کلی اثبات نشده‌است، ولی این حدس‌ها تا جایی می‌دانیم برای حالتی که شاخص رنگی حداقل باشد درست‌اند، حالتی که برای گراف‌های چندگانه با چندگانگی به اندازهٔ کافی بزرگ رخ می‌دهد.. الگوریتم‌های دقیق به راحتی می‌توان امتحان کرد که یک گراف را با یک رنگ یا دو رنگ می‌توان رنگ‌آمیزی یالی کرد یا نه. بنابراین اولین حالت غیربدیهی رنگ‌آمیزی یالی، امتحان کردن این است که گرافی ۳-رنگ‌آمیزی-یالی می‌شود یا نه. کوالیک(۲۰۰۹) نشان داد که می‌توان در زمان و با استفاده از حافظهٔ خطی، امتحان کرد یک گراف ۳-رنگ‌آمیزی-یالی دارد یا نه. با این که این زمان نمایی است، ولی بسیار بهتر و سریع‌تر از امتحان کردن تمام حالت‌های ممکن نسبت دادن رنگ‌ها به یال‌هاست. هر گراف ۲-همبند ۳-منتظم با رأس، از عدد ۳-رنگ‌آمیزی-یالی دارد، که تمام آن‌ها را می‌توان در زمان به دست‌آورد (قدری کندتر از زمان لازم برای پیدا کردن یک رنگ‌آمیزی)؛ همانطور که گرگ کوپربرگ مشاهده کرد، گراف یک منشور بر یک -ضلعی رنگ‌آمیزی‌های بسیاری دارد، که نشان می‌دهد این حد و مرز محکم است.. از آن‌جایی که رنگ‌آمیزی یالی حتی برای سه رنگ هم ان‌پی کامل است، بعید است که وقتی که بر حسب تعداد رنگ‌ها پارامتری شود، مهارشدنی با پارامتر ثابت باشد. در عمل، زو، ناکانو و نیشیزکی(۱۹۹۶) نشان دادند که برای گراف‌هایی با عرض درختی ، یک رنگ‌آمیزی بهینهٔ یالی در زمان قابل محاسبه است، زمانی که بر حسب فرانمایی است ولی برحسب تعداد رأس‌ها فقط خطی است. نمهاسر و پارک(۱۹۹۱) مسئلهٔ رنگ‌آمیزی یالی را به عنوان یک برنامهٔ عدد صحیح فرمول بندی کردند و تجربهٔ خود را در استفاده از یک حل کنندهٔ برنامه‌نویسی عدد صحیح برای رنگ‌آمیزی یالی گراف‌ها توضیح دادند. دو دسته یال با رنگ‌های دیگر یا از چرخش ۴۰ درجه‌ای یال‌های کمرنگ به دست می‌آیند یا می‌توان یال‌های دور همیلتونی که با رنگ تیره نشان داده شده‌اند را یکی در میان رنگ کرد. یک گراف به صورت یکتا -رنگ‌پذیر-یالی است اگر بدون درنظرگرفتن جایگشت رنگ‌ها فقط یک راه برای تقسیم یال‌ها به کلاس رنگی وجود داشته باشد (بدون در نظر گرفتن جایگشت رنگ‌ها). اگرچه همه گراف‌های ۳-رنگ‌پذیر همواره دارای دقیقاً سه دور همیلتونی هستند اما برعکس این موضوع صادق نیست یعنی گراف‌هایی با سه دور همیلتونی وجود دارند که به صورت یکتا ۳-رنگ‌پذیر-یالی نیستند همانند گراف‌های تعمیم‌یافتهٔ پترسن برای . تنها گراف غیر مسطح ۳-رنگ‌پذیر-یالی است و فرضیه‌ای وجود دارد که گرافی دیگر وجود ندارد.. به‌طور مشخص هرگراف یک رنگ‌آمیزی یالی equitable دارد که در آن تعداد رنگ‌ها بهینه است و تعداد یال‌های هردورنگ متفاوت فقط یکی اختلاف داشته باشد. (Richer 2011) مسئله پیدا کردن رسم گراف را برای گراف مکعبی با این خصوصیت که همه یال‌های رسم شده دارای یکی از سه slop متفاوت باشد و هیچ دویالی بر روی یک خط نباشند. اگر رسمی از وجود داشته باشد، slopها می‌تواند به عنوان رنگ‌ها در گراف ۳-رنگ‌پذیر استفاده شود. همانطور که Richer نشان می‌دهد گراف دو بخشی ۳-منتظم با رنگ‌آمیزی تایت داده شده را می‌توان اینگونه رنگ کرد اگروتنهااگر گراف ۳-همبند باشد. همان‌گونه که شاخص رنگی به بیشترین درجه و بیشترین تعداد تطابق‌های گراف مرتبط است، به linear arboricity گراف G نیز مرتبط است که آن‌را با نشان می‌دهد کمترین تعداد جنگل‌های خطی است که یال‌های گراف قابل افراز به آن جنگل‌ها باشند. برای گراف با حداکثر درجه سه، همیشه مقدار دو می‌گیرد و بنابراین داریم که این همان حد قضیهٔ ویزینگ است; ; .. عدد تو، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی به این شرط است که در هر مسیر با طول زوج، دنبالهٔ رنگی نیمهٔ اول مسیر و نیمهٔ دوم آن متفاوت باشد. Arboricity یک گراف، کمترین تعداد رنگ لازم برای رنگ‌آمیزی است با این شرط که به جای اینکه هیچ دو یال مجاوری همرنگ نباشد، هیچ دو یالی که در یک دور قرار دارند همرنگ نباشند. رنگ‌آمیزی یالی لیستی، مسئله‌ایست که در آن گرافی داده شده‌است که در آن هر رأس، لیستی از رنگ‌ها را نگه می‌دارد و هدف پیدا کردن رنگ‌آمیزی یالی است بطوری که هر رأس با یکی از رنگ‌های لیست خودش رنگ شود. شاخص رنگی لیستی یک گراف، کوچکترین عددی مانند است بطوریکه اگر لیست رنگ‌ها حداقل رنگ داشته باشد، نحوه انتخاب رنگ از آن لیست فرقی نکند و درهرصورت رنگ‌آمیزی امکان‌پذیر باشد. Galvin این فرضیه را به‌طور عمومی اثبات می‌کند: در هر گراف دو بخشی، مقادیر شاخص رنگی لیستی و شاخص رنگی با هم برابر است. برای مثال رنگ‌آمیزی یالی کامل نوع یالی از رنگ‌آمیزی کامل (نوعی رنگ‌آمیزی گراف که در آن هر جفت رنگ به حداقل یک جفت راس مجاور نسبت داده می‌شود و هدف بیشینه کردن تعداد تمام رنگ‌هاست) است.. | ## بخش 3: رنگ‌آمیزی یالی | رنگ‌آمیزی قوی یالی گراف نوع یالی از رنگ‌آمیزی قوی است که در آن به هر دو یالی که به یک رأس ختم می‌شوند باید رنگ‌های متفاوتی نسبت داده شود; ; ; .. رنگ‌آمیزی قوی یالی در زمینه‌هایی همچون تخصیص شمای کانال در شبکه‌های بی‌سیم کاربرد دارد.. رنگ‌آمیزی بدون دور یالی یکی از انواع رنگ‌آمیزی بدون دور است که در آن هردو کلاس رنگی، یک زیرگراف بدون دور را تشکیل می‌دهد (که یک جنگل است); .. وی نشان داد که وجود رنگ برای این مسئله معادل رسم گراف در محیط سه بعدی شطرنجی است که در آن یال‌های موازی معادل محورهای هم پایه و پایه‌های موازی شامل حداکثر دو یال می‌شود. رنگ‌آمیزی تام، شکلی از رنگ‌آمیزی است که از ترکیب رنگ‌آمیزی یالی و رأسی به وجود آمده است و باید همه راس‌ها و یال‌ها رنگ شوند. هر زوج رأس و یال مجاور یا دویال مجاور و همچنین هر دو رأس مجاور باید رنگ‌های متفاوتی داشته باشند. فرضیه‌ای اثبات نشده از ترکیب قضیهٔ ویزینگ و brooks به وجود می‌آید که می‌گوید برای هر گراف، تعداد رنگ‌های لازم برای رنگ‌آمیزی تام برابر بیشترین درجه گراف به‌اضافه دو است. اگر گراف ۳-منتظم روی یک سطح با سه رنگ قابل رنگ‌آمیزی باشد، گراف مکمل آن که سطح را به مثلث‌های هم‌مساحت افراز می‌کند نیز قابل رنگ‌آمیزی یالی است (هرچند در حالت کلی، ممکن است رنگ‌آمیزی نادرست یالی باشد). دیگر رنگ‌آمیزی‌ها و چرخش‌های مثلث‌ها با محدودیت‌ها خاص بر روی چگونگی مرتب‌شدن رنگ‌های رئوس، می‌تواند برای کد کردن انواع مختلف اشکال هندسی به کار برده شود. برای مثال تقسیم مستطیلی (تقسیم به مستطیل‌های کوچکتر بطوری که هر سه مستطیل کنار هم در یک رأس مشترک باشند) را می‌توان درقالب برچسب‌گذاری منظم به صورت رنگ‌آمیزی دوتایی یال‌های مستطیل مکمل تعریف کرد با این محدودیت که هر یال در برخورد با هر رأس، چهار زیرمجموعهٔ پیوسته را ایجاد می‌کند که در آن‌ها رنگ‌آمیزی‌ها یکسان است. این برچسب‌گذاری، مکمل رنگ‌آمیزی مستطیلی است که در آن هر یال عمودی یک رنگ و هریال افقی نیز رنگ دیگری دارد. برای هریک از این سه نوع برچست‌گذاری منظم، مجموعه‌ای از گراف‌های برچسب‌گذاری شده یک شبکه توزیع شده را تشکیل می‌دهند که برای لیست کردن سریع ساختارهای هندسی براساس همان گراف یا پیدا کردن محدودیت‌های بیشتر به کار می‌رود.. (Trahtman 2009) این مسئله را با اثبات این مطلب که اگر گراف قویاً همبند و نامتناوب باشد چنین رنگ‌آمیزی وجود دارد، حل کرده‌است. بر اساس این تئوری عددی مانند وجود دارد که هرگاه رنگ‌آمیزی امکان‌پذیر نخواهد بود. کاربردها برای زمان‌بندی مسابقات گردشی می‌توان رنگ‌آمیزی یالی یک گراف کامل را به کار برد. بدین صورت می‌توان در کمترین تعداد گردش این مسابقات را زمان‌بندی کرد بطوری که همه تیم‌ها در هر گردش بازی کنند. بنابراین تعداد گردش‌ها برابراست با تعداد رنگ‌های مورد استفاده برای رنگ‌آمیزی یالی.. برای زمان‌بندی مسابقاتی که همهٔ تیم‌ها با یکدیگر بازی نمی‌کند نیز می‌توان از تکنیک‌های دیگر رنگ‌آمیزی یالی استفاده کرد. برای مثال در لیگ جهانی فوتبال، جفت تیم‌هایی که باید در طول یک سال با هم بازی کنند، براساس نتایج سالیان قبلی تعیین می‌شود. زمان‌بندی بازی‌ها از اجرای الگوریتم رنگ‌آمیزی یالی بر روی گرافی به دست می‌آید که از جفت تیم‌ها ساخته شده‌است... برای این کاربرد، قضیهٔ ویزینگ بیان می‌کند که مستقل از این که جفت تیم‌ها چگونه انتخاب شده باشند (به شرط این که هیچ دو تیمی در یک فصل دو بار با هم بازی نکنند)، همواره می‌توان زمان‌بندی‌ای استفاده کرد که حداکثر یک هفته بیشتر از تعداد تیم‌ها طول بکشد. در این مسئله، مجموعه‌ای از محصولات باید تولید شوند و هر محصول برای تولید نیازمند اجرای مجموعه‌ای از وظایف است. هر وظیفه باید روی ماشین‌های خاصی اجرا شود و زمان‌بندی باید به صورتی انجام شود که وظایف به یک ماشین به‌طور همزمان نیاز نداشته باشند. اگر همه وظایف طول یکسانی داشته باشند، در این صورت مسئله به رنگ‌آمیزی گراف دوبخشی‌ای مدل می‌شود که رئوس در یک بخش گراف نشان‌دهندهٔ محصولات و رئوس بخش دیگر نشان‌دهنده ماشین‌ها هستند و یال‌ها نشان‌دهندهٔ وظایف هستند. از آن جایی که رنگ‌آمیزی گراف‌های دو بخشی در زمان چندجمله‌ای قابل انجام است، این مسئله نیز در زمان چندجمله‌ای قابل حل است.. در این مسئله باید بازه‌های زمانی برای یال‌های شبکه ارتباطی بی‌سیم انتخاب شود تا هر گره شبکه بتواند با گره‌های همسایه‌اش بدون تداخل ارتباط برقرار کند. استفاده از رنگ‌آمیزی یالی قوی (استفاده از دو بازه زمانی برای هر رنگ یال هریک برای یک جهت) مسئله را حل می‌کند ولی ممکن است تعداد بیشتری بازه زمانی مورد نیاز باشد. این گراف این خصوصیت را دارد که رنگ هر یال مستقیم با رنگ یال‌های دیگر و همچنین رنگ یال‌های همسایه‌های متفاوت باشد. آن‌ها برای این مسئله یک الگوریتم اکتشافی براساس الگوریتم توزیع شده برای -رنگ‌آمیزی-یالی پیشنهاد دادند. در ارتباطات فیبر نوری، رنگ‌آمیزی مسیر مسئله‌ایست که رنگ‌ها به جفت رئوسی که با هم ارتباط دارند، اختصاص می‌یابد. محدودیت این است که هیچ دو مسیری که قسمت مشترکی از فیبر را تسهیم می‌کنند از فرکانس یکسانی استفاده نکنند. مسیرها می‌توانند از سوئیچ ارتباطی یکسانی عبور کنند ولی از قسمت مشترکی از فیبر با فرکانس یکسان نمی‌توانند عبور کنند. وقتی توپولوژی شبکه به صورت ستاره‌ای باشد بدین صورت که سوئیچ در مرکز قرار دارد و هر گره با فیبرنوری جداگانه‌ای به سوئیچ متصل شده‌است، مسئلهٔ رنگ‌آمیزی مسیر تبدیل به رنگ‌آمیزی یالی گراف یا گراف چندگانه می‌شود. در این حالت گره‌ها همان رئوس گراف هستند و جفت گره‌هایی که با هم ارتباط برقرار می‌کنند، یال‌ها خواهند بود. تعداد رنگ‌های به کار رفته در رنگ‌آمیزی یالی، تعداد فرکانس‌های مورد استفاده در ارتباطات بین جفت گره‌هاست. برای ارتباطات شبکه‌ای با توپولوژی درختی، راه‌حل رنگ‌آمیزی مسیر برای شبکه‌های محلی حول هر سوئیچ به‌کاربرده می‌شود و از تجمیع این راه‌حل‌ها با یکدیگر مسئله نهایی حل خواهد شد.. مسائل باز جنسن و تافت(۱۹۹۵) لیستی از ۲۳ مسئلهٔ بار در رابطه با رنگ‌آمیزی یالی ارائه دادند. این لیست عبارت است از: حدس گلدبرگ(۱۹۷۳) که شاخص رنگی و شاخص کسری داخل یک‌دیگر هستند، که اجازهٔ تخمین زدن شاخص رنگی درون یک رنگ در زمان چندجمله‌ای را نمی‌دهد. چندین حدس از جیکوبسن و دیگران در ساختن گراف‌های بحرانی برای رنگ‌آمیزی یالی، گراف‌هایی از کلاس ۲ که هر زیرگرافی از آن‌ها یا بیشینه درجهٔ کمتر دارد یا از کلاس ۱ است. جیکوبسن در اصل حدس زد که تمامی گراف‌های بحرانی تعداد رأس‌هایشان فرد است، ولی این حدس بعدها به مرور رد شد. بسیاری از حدس‌های دیگری که این حدس را ضعیف می‌کنند، یا حد گذاشتن روی تعداد رأس‌های گراف‌های بحرانی و گراف‌های چندگانهٔ بحرانی، باز باقی‌مانده‌اند. مسئلهٔ ویزینگ که مسئلهٔ دسته‌بندی بیشینه درجاتی است که برای گراف‌های مسطح کلاس ۲ ممکن هستند. هیلتون، بیانگر این که گراف‌هایی با درجهٔ حداقل یا از کلاس ۱ هستند یا دارای زیرگرافی با بیشینه درجهٔ برابر با گراف اصلی و تعداد فرد رأس هستند، که تعداد یال‌های این زیرگراف بیشتر از است، و حدسی مشابه این حدس از Herbert Grötzsch و پاول سیمور در رابطه با گراف‌های مسطح به جای گراف‌هایی با درجهٔ زیاد. حدسی از چتویند و هیلتون (که احتمالاً به کار گابریل آندرو دیراک برمی‌گردد) که گراف‌های منتظم با تعداد زوج رأس و درجهٔ حداقل از کلاس ۱ هستند. فالکرسن که گراف‌های چندگانهٔ ۶-منتظم که از دوتا کردن هر یال یک گراف سادهٔ ۳-منتظم بدون پل به دست آمده است، ممکن است با ۶ رنگ رنگ‌آمیزی یالی شوند. حدسی از فیورینی و ویلسون که هر گراف مسطح بدون مثلث، به جز پنجهٔ K۱٬۳ به‌طور یکتا ۳-رنگ‌پذیر نیست. یک حدس اخیر این است که اگر گراف چندگانهٔ -منتظم مسطح باشد، آن‌گاه ، -رنگ‌پذیر است اگر و فقط اگر ، -همبند یالی باشد. | ## جمع‌بندی | ماریا چادنوسکی، کاترین ادواردز و پاول سیمور ثابت کردند که یک گراف چندگانهٔ ۸-منتظم یک عدد رنگی یالی ۸ دارد.