قانون رنگآمیزی رأس را دقیق بنویس
دو رأس مجاور باید رنگ متفاوت داشته باشند. رأسهای نامجاور میتوانند همرنگ باشند. شکل نزدیک دو رأس یا عبور خطها از کنار هم، بدون یال مشترک مجاورت ایجاد نمیکند.
کران بالا: یک رنگآمیزی با k رنگ بساز | کران پایین: ساختاری پیدا کن که دستکم k رنگ لازم دارد
عدد رنگی را کمینه بدان
اگر گراف را با چهار رنگ رنگ کردی، فقط ثابت کردهای عدد رنگی حداکثر چهار است. شاید سه یا دو رنگ کافی باشد. کمینهبودن نیاز به استدلال جدا دارد.
از رأس پرهمسایه شروع کن
در روش حریصانه، انتخاب رأس با محدودیت بیشتر میتواند تصمیمها را روشن کند. رنگی را بده که با همسایههای رنگشده تعارض نداشته باشد. ترتیب رأسها ممکن است تعداد رنگ روش حریصانه را تغییر دهد.
کلیک کران پایین میسازد
اگر k رأس دوبهدو مجاور باشند، هر کدام رنگ متفاوت لازم دارد؛ پس عدد رنگی دستکم k است. یافتن یک مثلث فوراً نشان میدهد دو رنگ کافی نیست.
گراف دوبخشی را با دو دسته بساز
اگر رأسها را بتوان به دو مجموعه تقسیم کرد که هر یال میان دو مجموعه باشد، گراف دوبخشی و با وجود دستکم یک یال دورنگپذیر است. رنگها را بر اساس دو دسته بده.
دور فرد مانع دورنگی است
در یک دور، رنگها باید یکیدرمیان عوض شوند. اگر طول دور فرد باشد، هنگام بازگشت دو رأس مجاور همرنگ میشوند؛ پس گراف دارای دور فرد دوبخشی نیست.
نمونهٔ مثلث
سه رأس یک مثلث هر کدام با دو رأس دیگر مجاورند، پس سه رنگ لازم دارند. ارائهٔ سه رنگآمیزی مجاز کران بالا و وجود کلیک سهرأسی کران پایین را میدهد؛ بنابراین عدد رنگی ۳ است.
درخت را دو رنگ کن
هر درخت دارای یال دوبخشی است. از یک رأس آغاز کن، فاصلهٔ زوج و فرد از آن را در دو گروه قرار بده و رنگها را یکیدرمیان بده. نبود دور ناسازگار، تعارض را حذف میکند.
مسئلهٔ زمانبندی را به گراف تبدیل کن
هر فعالیت یا آزمون را رأس و هر تعارض را یال بگیر. رنگ یک زمان یا منبع مشترک است. فعالیتهای مجاور نمیتوانند همزمان باشند و عدد رنگی کمترین تعداد بازه در مدل ساختهشده است.
کنترل نهایی یالبهیال
برای هر یال دو رنگ دو سر را بررسی کن و سپس دلیل کمینهبودن را بنویس. برای همسایگی از ماتریس مجاورت و برای درخت از درخت و درخت فراگیر کمک بگیر.