قضیه پنج رنگ
الگوریتم پنج رنگ کردن در زمان خطی

در سال ۱۹۹۶، رابرتسون، ساندرز، سیمور و توماس یک الگوریتم چهار رنگ کردن از درجه دوم در «گراف مسطح کارآمد چهار رنگ کردن» خود تعریف کردند. در همان‌جا، آن‌ها مختصراً یک الگوریتم پنج رنگ کردن در زمان خطی تعریف کردند که به طور مجانبی بهینه بود. الگوریتمی که در این جا توصیف شده بر روی چند گراف عمل می‌کند و بر قابلیت داشتن چندین نسخه از یال‌ها بین یک جفت رأس تکیه دارد. این قضیه بر اساس قضیه ورنیک می‌باشد که در پایین آمده است:
قضیه ورنیک: فرض می‌کنیم G یک گراف مسطح غیر خالی است که هیچ منطقه‌ای ندارد که با دو یال محدود شده باشد و حداقل درجه پنج دارد. پس G حتماً یک رأس از درجه پنج دارد که مجاور رأسی با درجه حداکثر شش است.
ما نمایشی از این گراف را به کار می‌بریم که در آن هر رأس یک لیست پیوندی دایره‌ای از رئوس مجاور را در جهت ساعتگرد گراف مسطح نگه می‌دارد.
در مفهوم، الگوریتم بازگشتی است؛ در هر مرحله گراف را به یک گراف با یک رأس کمتر کاهش می‌دهد؛ آن را پنج رنگ می‌کند و سپس از آن رنگ کردن استفاده می‌کند تا معین کند رنگ کردن گراف بزرگتر در زمان ثابتی انجام می‌شود. در عمل بیش از این که برای هر گراف کوچک شده، نمایش یک گراف صریح را نگه داریم، ما رئوس را از گراف حذف می‌کنیم و آن‌ها را به یک پشته اضافه می‌کنیم. سپس در آخر هنگامی که آن‌ها را از پشته خارج می‌کنیم، رنگشان می‌کنیم. ما سه تا پشته را نگه خواهیم داشت:
S4: همه رئوس باقی‌مانده با درجه حداکثر چهار یا درجه پنج و حداکثر چهار رأس مجاور مجزا (بسته به یال‌ها چندگانه) را در بردارد.
S5: همه رئوس باقی‌مانده که درجه پنج، پنج رأس مجاور مجزا و حداقل یک رأس مجاور با درجه حداکثر شش دارند را در بر می‌گیرد.
Sd: همه رئوسی که قبلاً از گراف حذف شده‌اند را به ترتیب حذف شدنشان شامل می‌شود.
الگوریتم به نحوه زیر کار می‌کند:
در گام اول، ما همه یال‌های چندگانه را به یال‌های تکی تقلیل می‌دهیم تا گراف ساده شود. سپس ما بر روی رئوس گراف تکرار می‌زنیم تا رئوسی را که با شرایط بیان شده برای S4 و S5 مطابقت دارند را در پشته مربوطه قرار دهیم.
سپس تا هنگامی که S4 خالی نشده است، ما رأس v را از S4 بیرون می‌کشیم و v را از گراف حذف می‌کنیم و آن را به همراه لیستی از همسایگانش در این زمان به Sd داخل می‌کنیم. ما هر همسایه قبلی v را بررسی می‌کنیم و در صورت لزوم آن را به S4 و S5 وارد می‌کنیم.
هنگامی که S4 خالی شد، می‌دانیم که گرافمان کمینه درجه پنج را داراست. اگر گراف خالی بود، ما به گام ۵ که در زیر آمده است می‌رویم. در غیر این صورت قضیه ورنیک به ما می‌گوید که S5 خالی نیست. v را از S5 بیرون می‌کشیم و آن را از گراف حذف می‌کنیم و v 1 و v 2 و v 3 و v 4 و v 5 را در گراف مسطح به صورت ساعتگرد همسایگان v می‌گذاریم که v 1 همسایه با درجه حداکثر شش است. ما مجاور بودن v 1 و v 3 را بررسی می‌کنیم (این کار با توجه به درجه v 1 در زمان ثابت انجام می‌شود). دو حالت وجود دارد:
اگر v1 مجاور با v3 نباشد، ما می‌توانیم این دو رأس را به یک تک رأس ادغام کنیم. برای انجام این کار ما رأس v را از هر دو لیست مجاورت دایره‌ای حذف می‌کنیم. سپس در جایی که v قبلاً بود، دو لیست را به هم متصل می‌کنیم. در صورتی که v ارجاعی از موقعیتش در هر لیست را نگه می‌دارد، این کار می‌تواند در زمان ثابت انجام شود. ممکن است faceهایی محدود به دو یال در نقاطی که لیست هایشان را ادغام کردیم، به وجود بیاید که ما یک یال از این چنین faceها حذف می‌کنیم. پس از انجام این کار، ما v3 را به Sd وارد می‌کنیم با توجه به این که v1 رأسی است که با آن ادغام شده بود. هر رأسی که مورد تأثیر قرار گرفته از ادغام، در زمان مناسب در پشته اضافه شده یا کم می‌شود.
در غیر این صورت v2 درون منطقه‌ای قرارگرفته که با v و v1 و v3 مشخص شده است. در نتیجه v2 نمی‌تواند مجاور با v4 که در خارج از این منطقه واقع است. ما v2 و v4 را به روشی مشابه با v1 و v3 که در بالا آمد ادغام می‌کنیم.
به گام ۲ برو.
در این جا، S4 و S5 و گراف خالی شده‌اند. ما رئوس را از Sd بیرون می‌کشیم؛ اگر رأس با رأس دیگری در گام ۳ ادغام شده بود، رأسی که با آن ادغام شده بود، پیش تر رنگ شده است و ما به آن رنگ مشابه می‌دهیم. این کار مجاز است زیرا ما تنها رئوسی را ادغام کرده بودیم که در گراف اصلی مجاور نبودند. اگر ما آن را در گام ۲ به دلیل این که حداکثر چهار رأس مجاور داشته، حذف کرده بودیم، همه همسایگانش در زمان حذف، رنگ شده خواهند بود و ما به سادگی می‌توانیم به آن رنگی که هیچ‌کدام از همسایگانش نگرفته‌اند را بدهیم.