کسی بھی نقشے کے لیے چار رنگ کافی ہیں، اس طرح کہ پڑوسی ہمیشہ مختلف ہوں۔ یہ 1976 میں ثابت ہوا۔ مگر عملاً یہ رنگ ڈھونڈے کیسے جائیں؟
روایتی آلہ کیمپے زنجیر (Kempe chain) ہے۔ دو رنگ چنیے۔ صرف انہی دو میں رنگے ممالک کا پورا جڑا ہوا ٹکڑا لیجیے۔ پورے ٹکڑے میں انہیں آپس میں بدل دیجیے: نقشہ درست رنگا ہوا ہی رہتا ہے۔
مشکل یہ ہے: ایک ہی تبادلہ پورے نقشے میں لہر کی طرح پھیل سکتا ہے۔ پچھلے ریکارڈ کو نقشے بڑے ہونے کے ساتھ زیادہ تبادلوں کی ضرورت پڑتی تھی۔ ہر تبادلے کی قیمت پورے نقشے سے ایک بار گزرنا تھی۔
ٹوکیو سے کوپن ہیگن تک کے چھ ریاضی دانوں نے یہ اضافی لاگت ختم کر دی ہے۔ ان کا الگورتھم n ممالک کو n کے متناسب وقت میں رنگتا ہے۔ نقشے کے چھوٹے ٹکڑے ایک بار حل کیے جاتے ہیں، جدولوں میں محفوظ کیے جاتے ہیں، پھر بس ان میں دیکھ لیے جاتے ہیں۔ مصنفین اس رفتار کو بہترین ممکن (optimal) کہتے ہیں۔
ماخذ: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










