رنگ‌آمیزی یالی
الگوریتم‌ها > الگوریتم‌هایی که از تعداد رنگ بیشتر از تعداد بهینه استفاده می‌کنند

میسرا و گریس (۱۹۹۲) و گابو و همکاران (۱۹۸۵) الگوریتم‌هایی با زمان چندجمله‌ای برای رنگ کردن هر گراف با Δ + ۱ رنگ ارائه می‌دهند که حد بالایی قضیهٔ ویزینگ است.
برای گراف‌های چندگانه، کارلوف و شمویس(۱۹۸۷) الگوریتمی ارائه دادند که به اِلی آپفال نسبت دادند. در این الگوریتم ابتدا گراف چندگانهٔ G با اضافه کردن یک رأس و متصل کردن آن به همهٔ رأس‌های فرد، گراف اویلری می‌شود، دور اویلری پیدا می‌شود، و یک جهت برای دور انتخاب می‌شود. سپس یک گراف دو بخشی H که هر بخشش یک کپی از رأس‌های G است درست می‌شود، و یک یال از رأس u در بخش چپ به رأس v در بخش راست رسم می‌شود اگر و فقط اگر دور اویلری جهت دار یک یال از u به v در G داشته باشد. H با یک رنگ‌آمیزی یالی برای گراف‌های دوبخشی رنگ می‌شود. هر دسته رنگ در H متناظر یک دسته یال در G می‌شود که بیشینه درجهٔ دو دارد؛ که یک اجتماعی از مسیرها و دورهای جدا از هم است. بنابراین به هر دسته رنگ در H می‌توان سه دسته رنگ در G نسبت داد. زمان این الگوریتم بستگی به زمان رنگ‌آمیزی یالی یک گراف دو بخشی دارد که با استفاده از الگوریتم کول، اُست و شیرا از O(m log Δ) است. تعداد رنگ‌هایی که این الگوریتم استفاده می‌کند حداکثر   3\left\lceil {\frac {\Delta }{2}}\right\rceil  است، که نزدیک ولی نه دقیقاً برابر حد شانون  \left\lfloor {\frac {3\Delta }{2}}\right\rfloor  است. این الگوریتم همچنین به طریقی سرراست می‌تواند به یک الگوریتم موازی تبدیل شود. در یک مقاله، کارلوف و شمویس همچنین یک الگوریتم خطی برای رنگ کردن گراف‌های چندگانه از بیشینه درجهٔ سه با چهار رنگ ارائه می‌کنند (که با هر دو حد ویزینگ و شانون مطابقت دارد) و بر پایه‌های ساده استوار است: این الگوریتم یک رأس به گراف اضافه می‌کند تا گراف اویلری شود، یک دور اویلری پیدا می‌کند، و سپس متناوباً مجموعه‌هایی از یال‌ها را روی دور پیدا می‌کند به طوری که گراف به دو زیرگراف از بیشینه درجهٔ دو تقسیم شود. مسیرها و دورهای زوج هر زیرگراف را با دو رنگ می‌توان رنگ کرد. پس از این مرحله، هر کدام از دورهای فرد باقی‌مانده حداقل یک یال دارند که می‌توان آن را با یکی از دو رنگی که متعلق به زیرگراف دیگر است، رنگ کرد. این یال از دور فرد حذف می‌شود که در نتیجه یک مسیر باقی می‌ماند که با دو رنگ زیرگراف خود رنگ شده‌است.
یک الگوریتم حریصانه که یال‌های گراف را یکی یکی بررسی می‌کند و به هر کدام اولین رنگ موجود را نسبت می‌دهد، گاهی تا ۲Δ − ۱ عدد رنگ مصرف می‌کند که تقریباً دو برابر تعداد رنگ‌های مورد نیاز است. اما این برتری را دارد که می‌توان از این الگوریتم در زمینهٔ الگوریتم برخط استفاده کرد که در آن گراف ورودی از قبل مشخص نیست. در این زمینه، نسبت رقابتی این الگوریتم دو است که بهینه است: هیچ الگوریتم برخط دیگری نتوانسته است عملکرد بهتری داشته باشد. ولی اگر یال‌ها به ترتیبی رندم وارد شوند و گراف ورودی درجه‌ای حداقل لگاریتمی داشته باشد، آن‌گاه می‌توان به نسبت‌های رقابتی بهتری دست یافت.
تعدادی از مؤلفین حدس زده‌اند که بیان می‌کند که شاخص رنگی کسری هر گراف چندگانه (یک عدد که بتوان در زمان چندجمله‌ای با استفاده از برنامه‌نویسی خطی حساب کرد) یکی از شاخص‌های رنگی است. اگر این حدس‌ها درست باشد، این امکان وجود دارد که عددی را بتوان محاسبه کرد که برای مورد گراف‌های چندگانه هیچ‌گاه بیشتر از یک عدد از شاخص رنگی بیشتر نباشد، که در مورد گراف‌های ساده تطابق است: تا جایی که از طریق قضیهٔ ویزینگ می‌دانیم. با این که در حالت کلی اثبات نشده‌است، ولی این حدس‌ها تا جایی می‌دانیم برای حالتی که شاخص رنگی حداقل  \Delta +{\sqrt {\Delta /2}} باشد درست‌اند، حالتی که برای گراف‌های چندگانه با چندگانگی به اندازهٔ کافی بزرگ رخ می‌دهد.