أربعة ألوان تكفي لأي خريطة، بحيث يختلف لون الجيران دائمًا. أُثبت ذلك عام 1976. لكن كيف نجد هذه الألوان فعلًا؟
الأداة الكلاسيكية هي سلسلة كمبه. اختر لونين وخُذ الرقعة المتّصلة كلها من البلدان الملوّنة بهذين اللونين وحدهما. بادِل بينهما في الرقعة كلها: تبقى الخريطة ملوّنة تلوينًا صحيحًا.
المشكلة: قد يمتدّ أثر مبادلة واحدة عبر الخريطة كلها. وكان الرقم القياسي السابق يحتاج إلى مزيد من المبادلات كلما كبرت الخرائط. وكانت كل مبادلة تكلّف مرورًا كاملًا على الخريطة.
أزال ستة رياضيين، من طوكيو إلى كوبنهاغن، هذه الكلفة الإضافية. فخوارزميتهم تلوّن n من البلدان في زمن يتناسب مع n. تُحلّ القطع الصغيرة من الخريطة مرة واحدة، وتُخزَّن في جداول، ثم يُرجَع إليها ببساطة. ويصف المؤلفون هذه السرعة بأنها مُثلى.
المصدر: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










