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

عدد تو، تعداد رنگ‌های لازم برای رنگ‌آمیزی یالی به این شرط است که در هر مسیر با طول زوج، دنبالهٔ رنگی نیمهٔ اول مسیر و نیمهٔ دوم آن متفاوت باشد. Arboricity یک گراف، کمترین تعداد رنگ لازم برای رنگ‌آمیزی است با این شرط که به جای اینکه هیچ دو یال مجاوری همرنگ نباشد، هیچ دو یالی که در یک دور قرار دارند همرنگ نباشند. این عدد بیانگر کمینه تعداد تقسیم‌بندی گراف به جنگل است. برخلاف شاخص رنگی، مقدار Arboricity را می‌توان در زمان چندجمله‌ای محاسبه کرد.
رنگ‌آمیزی یالی لیستی، مسئله‌ایست که در آن گرافی داده شده‌است که در آن هر رأس، لیستی از رنگ‌ها را نگه می‌دارد و هدف پیدا کردن رنگ‌آمیزی یالی است بطوری که هر رأس با یکی از رنگ‌های لیست خودش رنگ شود. شاخص رنگی لیستی یک گراف، کوچکترین عددی مانند k است بطوریکه اگر لیست رنگ‌ها حداقل k رنگ داشته باشد، نحوه انتخاب رنگ از آن لیست فرقی نکند و درهرصورت رنگ‌آمیزی امکان‌پذیر باشد. بنابراین شاخص رنگی لیستی همواره از شاخص رنگی ناکوچکتر است.Dinitz conjecture در تکمیل مربع لاتین، شاخص رنگی لیستی در گراف‌های کامل دوبخشی را برابر با شاخص رنگی تعریف می‌کند. Galvin این فرضیه را به‌طور عمومی اثبات می‌کند: در هر گراف دو بخشی، مقادیر شاخص رنگی لیستی و شاخص رنگی با هم برابر است. این مسئله برای هر گراف دوبخشی دلخواه بدون دور کماکان بدون اثبات باقی‌مانده است.
تعداد زیادی از مسائل رنگ‌آمیزی رئوس قابل گسترش به رنگ‌آمیزی یالی است. برای مثال رنگ‌آمیزی یالی کامل نوع یالی از رنگ‌آمیزی کامل (نوعی رنگ‌آمیزی گراف که در آن هر جفت رنگ به حداقل یک جفت راس مجاور نسبت داده می‌شود و هدف بیشینه کردن تعداد تمام رنگ‌هاست) است. رنگ‌آمیزی قوی یالی گراف نوع یالی از رنگ‌آمیزی قوی است که در آن به هر دو یالی که به یک رأس ختم می‌شوند باید رنگ‌های متفاوتی نسبت داده شود. رنگ‌آمیزی قوی یالی در زمینه‌هایی همچون تخصیص شمای کانال در شبکه‌های بی‌سیم کاربرد دارد. رنگ‌آمیزی بدون دور یالی یکی از انواع رنگ‌آمیزی بدون دور است که در آن هردو کلاس رنگی، یک زیرگراف بدون دور را تشکیل می‌دهد (که یک جنگل است).
(Eppstein 2008) دربارهٔ رنگ‌آمیزی یالی سه‌گانه برای گراف‌های مکعبی با خصوصیات اضافی مطالعه کرد. در این رنگ‌آمیزی هیچ دو دور bichromaticی که بیش از یک یال مشترک دارند، وجود ندارد. وی نشان داد که وجود رنگ برای این مسئله معادل رسم گراف در محیط سه بعدی شطرنجی است که در آن یال‌های موازی معادل محورهای هم پایه و پایه‌های موازی شامل حداکثر دو یال می‌شود. البته ذکر این نکته ضروری است که حل این مسئله نیز مانند حل مسئله استاندارد رنگ‌آمیزی سه‌گانه NP-complete است.
رنگ‌آمیزی تام، شکلی از رنگ‌آمیزی است که از ترکیب رنگ‌آمیزی یالی و رأسی به وجود آمده است و باید همه راس‌ها و یال‌ها رنگ شوند. هر زوج رأس و یال مجاور یا دویال مجاور و همچنین هر دو رأس مجاور باید رنگ‌های متفاوتی داشته باشند. فرضیه‌ای اثبات نشده از ترکیب قضیهٔ ویزینگ و brooks به وجود می‌آید که می‌گوید برای هر گراف، تعداد رنگ‌های لازم برای رنگ‌آمیزی تام برابر بیشترین درجه گراف به‌اضافه دو است.
اگر گراف ۳-منتظم روی یک سطح با سه رنگ قابل رنگ‌آمیزی باشد، گراف مکمل آن که سطح را به مثلث‌های هم‌مساحت افراز می‌کند نیز قابل رنگ‌آمیزی یالی است (هرچند در حالت کلی، ممکن است رنگ‌آمیزی نادرست یالی باشد). رنگ‌آمیزی بدین صورت انجام می‌گیرد که هر مثلث یک یال از هر رنگ را دارد. دیگر رنگ‌آمیزی‌ها و چرخش‌های مثلث‌ها با محدودیت‌ها خاص بر روی چگونگی مرتب‌شدن رنگ‌های رئوس، می‌تواند برای کد کردن انواع مختلف اشکال هندسی به کار برده شود. برای مثال تقسیم مستطیلی (تقسیم به مستطیل‌های کوچکتر بطوری که هر سه مستطیل کنار هم در یک رأس مشترک باشند) را می‌توان درقالب برچسب‌گذاری منظم به صورت رنگ‌آمیزی دوتایی یال‌های مستطیل مکمل تعریف کرد با این محدودیت که هر یال در برخورد با هر رأس، چهار زیرمجموعهٔ پیوسته را ایجاد می‌کند که در آن‌ها رنگ‌آمیزی‌ها یکسان است. این برچسب‌گذاری، مکمل رنگ‌آمیزی مستطیلی است که در آن هر یال عمودی یک رنگ و هریال افقی نیز رنگ دیگری دارد. برای هریک از این سه نوع برچست‌گذاری منظم، مجموعه‌ای از گراف‌های برچسب‌گذاری شده یک شبکه توزیع شده را تشکیل می‌دهند که برای لیست کردن سریع ساختارهای هندسی براساس همان گراف یا پیدا کردن محدودیت‌های بیشتر به کار می‌رود.
یک deterministic finite automaton به عنوان یک گراف مستقیم تفسیر می‌شود که در آن هر رأس درجهٔ خروجی d را دارد و یال‌ها d-رنگ‌پذیرند بطوری که یال‌ها با رأس مبدأ مشترک، رنگ‌ها متفاوتی دارند. مسئلهٔ رنگ‌آمیزی جاده‌ها، مسئلهٔ رنگ‌آمیزی یالی گراف مستقیم است که automatonهای را نتیجه می‌دهد که synchronizing word دارند. (Trahtman 2009) این مسئله را با اثبات این مطلب که اگر گراف قویاً همبند و نامتناوب باشد چنین رنگ‌آمیزی وجود دارد، حل کرده‌است.
تئوری Ramsey به مسئلهٔ رنگ‌آمیزی k-تایی گراف کامل Kn مربوط می‌شود که از ساختن زیرگراف کامل Ks از سایز داده شدهٔ s که monochromatic باشد جلوگیری می‌کند. بر اساس این تئوری عددی مانند Rk(s) وجود دارد که هرگاه n ≥ R(s) رنگ‌آمیزی امکان‌پذیر نخواهد بود. برای مثال در گراف K۶ با R۲(۳) = ۶ اگر یال‌ها ۲-رنگ‌شده باشد، حتماً مستطیل monochromatic وجود دارد.