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










