किसी भी नक़्शे के लिए चार रंग काफ़ी हैं, ताकि पड़ोसी हमेशा अलग रंग के हों। यह 1976 में सिद्ध हुआ। पर असल में वे रंग ढूँढ़े कैसे जाएँ?
क्लासिक औज़ार है केम्पे शृंखला। दो रंग चुनिए। सिर्फ़ इन्हीं दो रंगों वाले देशों का पूरा जुड़ा हुआ हिस्सा लीजिए। पूरे हिस्से में उन्हें आपस में बदल दीजिए: नक़्शा सही ढंग से रंगा ही रहता है।
पेच यह है: एक अदला-बदली पूरे नक़्शे में फैल सकती है। पिछले रिकॉर्ड को नक़्शे बड़े होने पर ज़्यादा अदला-बदली चाहिए थी। हर एक की क़ीमत थी पूरे नक़्शे से एक बार गुज़रना।
टोक्यो से कोपेनहेगन तक के छह गणितज्ञों ने यह अतिरिक्त लागत हटा दी है। उनका एल्गोरिद्म n देशों को n के अनुपाती समय में रंगता है। नक़्शे के छोटे टुकड़े एक बार हल किए जाते हैं, तालिकाओं में रखे जाते हैं, फिर बस देख लिए जाते हैं। लेखक इस गति को इष्टतम कहते हैं।
स्रोत: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










