چهار رنگ برای هر نقشه کافی است، طوری که همسایهها همیشه با هم فرق کنند. این در 1976 اثبات شد. اما رنگها را در عمل چگونه پیدا کنیم؟
ابزار کلاسیک زنجیرهٔ کمپه (Kempe chain) است. دو رنگ انتخاب کنید. کل ناحیهٔ پیوستهٔ کشورهایی را بگیرید که فقط با این دو رنگ شدهاند. در سراسر این ناحیه جایشان را عوض کنید: نقشه درست رنگآمیزیشده باقی میماند.
مشکل اینجاست: یک جابهجایی میتواند در سراسر نقشه موج بیندازد. رکورد پیشین با بزرگتر شدن نقشهها به جابهجاییهای بیشتری نیاز داشت. هر یک به بهای یک پیمایش کامل نقشه تمام میشد.
شش ریاضیدان، از توکیو تا کپنهاگ، این هزینهٔ اضافی را حذف کردهاند. الگوریتم آنها n کشور را در زمانی متناسب با n رنگ میکند. تکههای کوچک نقشه یک بار حل میشوند، در جدولها ذخیره میشوند و سپس فقط از آنجا خوانده میشوند. نویسندگان این سرعت را بهینه میدانند.
منبع: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










