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

رنگ آمیزی یالی. در نظریهٔ گراف، یک رنگ آمیزی یالی از یک گراف، نسبت دادن "رنگ ها" به یال های گراف است به نحوی که هیچ دو یال مجاوری رنگ یکسان نداشته باشند. برای مثال، تصویر سمت چپ نمایانگر یک رنگ آمیزی یالی از یک گراف با رنگ های قرمز، آبی، و سبز است. رنگ آمیزی یالی یکی از انواع مختلف رنگ آمیزی گراف است. مسئلهٔ رنگ آمیزی یالی بررسی می کند که آیا ممکن است یال های یک گراف داده شده را با حداکثر k رنگ متفاوت که k داده شده است، یا با کمترین تعداد رنگ ممکن، رنگ کرد. کمترین تعداد لازم رنگ برای یال های یک گراف داده شده، شاخص رنگی آن گراف نامیده می شود. برای مثال، گراف تصویر با سه رنگ، رنگ می شود ولی نمی توان آن را با دو رنگ رنگ کرد، پس شاخص رنگی آن سه است.
حدس گلدبرگ(۱۹۷۳) که شاخص رنگی و شاخص کسری داخل یک دیگر هستند، که اجازهٔ تخمین زدن شاخص رنگی درون یک رنگ در زمان چندجمله ای را نمی دهد.
چندین حدس از جیکوبسن و دیگران در ساختن گراف های بحرانی برای رنگ آمیزی یالی، گراف هایی از کلاس ۲ که هر زیرگرافی از آن ها یا بیشینه درجهٔ کمتر دارد یا از کلاس ۱ است. جیکوبسن در اصل حدس زد که تمامی گراف های بحرانی تعداد رأس هایشان فرد است، ولی این حدس بعدها به مرور رد شد. بسیاری از حدس های دیگری که این حدس را ضعیف می کنند، یا حد گذاشتن روی تعداد رأس های گراف های بحرانی و گراف های چندگانهٔ بحرانی، باز باقی مانده اند.
مسئلهٔ ویزینگ که مسئلهٔ دسته بندی بیشینه درجاتی است که برای گراف های مسطح کلاس ۲ ممکن هستند.
حدس زیرگراف کاملاً پر از ای. جی. دبلیو. هیلتون، بیانگر این که گراف هایی با درجهٔ حداقل n/۳ یا از کلاس ۱ هستند یا دارای زیرگرافی با بیشینه درجهٔ Δ برابر با گراف اصلی و تعداد فرد k رأس هستند، که تعداد یال های این زیرگراف بیشتر از Δ(k − ۱)/۲ است، و حدسی مشابه این حدس از Herbert Grötzsch و پاول سیمور در رابطه با گراف های مسطح به جای گراف هایی با درجهٔ زیاد.
حدسی از چتویند و هیلتون (که احتمالاً به کار گابریل آندرو دیراک برمی گردد) که گراف های منتظم با تعداد زوج n رأس و درجهٔ حداقل n/۲ از کلاس ۱ هستند.
حدسی از کلاد برگ و دی. آر. فالکرسن که گراف های چندگانهٔ ۶-منتظم که از دوتا کردن هر یال یک گراف سادهٔ ۳-منتظم بدون پل به دست آمده است، ممکن است با ۶ رنگ رنگ آمیزی یالی شوند.
حدسی از فیورینی و ویلسون که هر گراف مسطح بدون مثلث، به جز پنجهٔ K۱٬۳ به طور یکتا ۳-رنگ پذیر نیست.
بنابر قضیهٔ ویزینگ، تعداد رنگ های لازم برای رنگ آمیزی یالی یک گراف ساده برابر با بیشترین درجهٔ آن Δ یا Δ+۱ است. برای برخی از گراف ها مانند گراف های دوبخشی یا گراف های مسطح با درجهٔ بالا تعداد رنگ های لازم همیشه Δ است؛ ولی برای گراف های چندگانه تعداد رنگ های ممکن است به بزرگی ۳Δ/۲ باشد. الگوریتم هایی با زمان های چندجمله ای وجود دارند که رنگ آمیزی بهینهٔ گراف های دوبخشی یا گراف های غیر دوبخشی ساده که حداکثر Δ+۱ رنگ لازم دارند را محاسبه می کند؛ در صورتی که مسئلهٔ کلی یافتن رنگ آمیزی بهینه ان پی کامل است و سریع ترین الگوریتم شناخته شده برای آن، زمان نمایی نیاز دارد. انواع دیگری از مسئلهٔ رنگ آمیزی یالی مطالعه شده اند که در آن ها نسبت دادن رنگ ها به یال ها باید شرایط دیگری غیر از نامجاور بودن را نیز برآورده کند. مسئلهٔ رنگ آمیزی گراف کاربردهایی در مسائل زمان بندی و نیز انتساب فرکانس برای شبکه های فیبرنوری دارد.
گراف دوری با طول دور زوج به دو رنگ و با طول فرد به سه رنگ برای رنگ آمیزی یالی نیاز دارد. در این گراف ها، رنگ آمیزی یالی به صورت یک درمیان صورت می گیرد.
در گراف کامل Kn با n زوج به n − ۱ رنگ نیاز داریم. رنگ آمیزی گراف کامل، حالت خاص (Baranyai’s theorem]] Soifer 2008]]) به شمار می رود که راه حل هندسی زیر را ارائه می دهد: n نقطه در مرکز یک n − ۱-ضلعی قرار دهید. به هر یال رأس مرکزی، رنگ متفاوتی را انتساب دهید. برای یال های دیگر رئوس نیز همین کار را با رعایت شروط رنگ آمیزی انجام دهید. درصورتی که n فرد باشد، برای رنگ آمیزی یالی به n رنگ نیاز داریم: هر رنگ برای (n − ۱)/۲ یال قابل استفاده است که این تعداد یال، ۱/n تعداد کل یال هاست.