گراف یالی

{line graph, covering graph, adjoint graph, derived graph, edge graph} [ریاضی] برای گراف مفروض G، گرافی مانند L(G ) که رأس های آن یال های G هستند و دو رأس درL(G ) به هم وصل می شوند، هرگاه یال های متناظر در Gدارای رأس مشترک باشند

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

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