किसी भी नक़्शे के चार रंग, रैखिक समय में

किसी समतल काग़ज़ पर बना कोई भी नक़्शा चार रंगों से इस तरह रंगा जा सकता है कि पड़ोसी देशों का रंग कभी एक न हो। Francis Guthrie ने 1852 में यह अनुमान रखा; Appel और Haken ने 1976 में इसे सिद्ध किया। पर प्रमेय केवल इतना कहता है कि चार रंग मौजूद हैं। किसी दिए गए नक़्शे के लिए उन्हें ढूँढ़ें कैसे? “इसका कोई आसान जवाब नहीं है,” टोक्यो विश्वविद्यालय के Yuta Inoue और जापान, कनाडा, स्लोवेनिया और डेनमार्क के उनके पाँच सहयोगी लिखते हैं। यह प्रश्न इतना उलझा रहा है कि इससे कई प्रस्तावित प्रति-उदाहरण पैदा हुए।

बिंदु, रेखाएँ और त्रिभुज

हर देश एक बिंदु, यानी शीर्ष (vertex), बन जाता है, और हर साझा सीमा एक रेखा, यानी कोर (edge): नक़्शा एक समतलीय ग्राफ़ (planar graph) बन जाता है, जिसे बिना किसी रेखा के एक-दूसरे को काटे बनाया जा सकता है। इसे रंगने का अर्थ है हर शीर्ष को चार में से एक रंग देना, ताकि हर कोर के दोनों सिरों पर रंग अलग हों। शीर्षों की संख्या को n कहिए। त्रिभुजीकरणों (triangulations) को सँभाल लेना काफ़ी है, जिनमें हर फलक एक त्रिभुज होता है: और कोर जोड़ने से रंगना केवल कठिन ही होता है।

केम्पे की अदला-बदली

मूल चाल A. B. Kempe के 1879 के एक शोधपत्र तक जाती है। चारों रंगों को जोड़ियों में बाँटिए, मान लीजिए लाल के साथ नीला और हरे के साथ पीला। केम्पे शृंखला (Kempe chain) शीर्षों का एक जुड़ा हुआ समूह है जिन पर किसी एक जोड़ी के दो रंग हों। पूरी शृंखला में उन दो रंगों को आपस में बदलने पर रंगाई वैध बनी रहती है।

एक शीर्ष v लीजिए जिसके चार पड़ोसी हैं, उसके चारों ओर क्रम से v0 से v3, और पहले बाक़ी हिस्से को रंग दीजिए। अगर पड़ोसी तीन या कम रंगों का इस्तेमाल करते हैं, तो v ख़ाली बचा रंग ले लेता है। अगर वे चारों रंग इस्तेमाल करते हैं, तो v0 और v2 के रंगों वाली उस शृंखला पर चलिए जो v0 से शुरू होती है। अगर वह v2 तक नहीं पहुँचती, तो उसमें अदला-बदली कीजिए: v0 को v2 का रंग मिल जाता है, और v के लिए एक रंग ख़ाली हो जाता है। अगर वह v2 तक पहुँच जाती है, तो इसके बजाय v1 और v3 के रंगों वाली v1 की शृंखला में अदला-बदली कीजिए, ताकि v1 को v3 का रंग मिल जाए।

टुकड़े जिन्हें हमेशा ठीक किया जा सकता है

प्रमेय के प्रमाण अपचेय विन्यासों (reducible configurations) पर टिके हैं: छोटे पैटर्न जिन्हें काटकर निकाला जा सकता है, और बाक़ी के रंगे जाने के बाद वापस रखा जा सकता है। अगर उनके वलय (ring) — ठीक उनके चारों ओर के शीर्षों — के रंग मेल नहीं खाते, तो बाहर किए गए सीमित संख्या के सुधारक केम्पे बदलाव उन्हें हमेशा ठीक कर देते हैं: यहाँ इस्तेमाल पैटर्नों के लिए अधिकतम 25, जिनके वलयों में अधिकतम 18 शीर्ष होते हैं।

एक अपचेय विन्यास (बाएँ; हर संख्या बताती है कि पूरे नक़्शे में उस शीर्ष के कितने पड़ोसी होने चाहिए) और वही पैटर्न अपने वलय R से पूरा किया हुआ (दाएँ)। — चित्र 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour और Thomas ने 1997 में दिखाया कि इस तरह, एक बार में एक पैटर्न लेकर, कैसे रंगा जाए। हर दौर ग्राफ़ को कुछ शीर्षों से छोटा करता है और उसकी क़ीमत पूरे ग्राफ़ से एक बार गुज़रना है, इसलिए समय द्विघाती (quadratic) होता है: दोगुने बड़े नक़्शे के लिए चार गुना अधिक।

एक पिछले शोधपत्र (FOCS’26) में इन्हीं छह लेखकों ने सिद्ध किया कि हर त्रिभुजीकरण में n के अनुपाती संख्या में एक-दूसरे को न छूने वाले अपचेय विन्यास होते हैं, जो 8,202 पैटर्नों की एक सूची से लिए गए हैं — या उतने ही छोटे लूप जिनके दोनों ओर शीर्ष हों, जो भी मदद करते हैं। वे सारे पैटर्न एक साथ हटाते हैं, बाक़ी को रंगते हैं, फिर सारे वलयों को एक साथ ठीक करते हैं। एक यादृच्छिक केम्पे बदलाव किसी दिए गए वलय की मदद करता है अगर वह रंगों की सही जोड़ी चुने (तीन में एक संभावना) और वलय को छूने वाली हर शृंखला पर सिक्का सही गिरे (हर एक पर दो में एक संभावना)। ऐसी अधिकतम 18 शृंखलाओं के साथ, यह कम से कम 3 × 2¹⁸ यानी 786,432 में एक संभावना है: छोटी, पर निश्चित। इसलिए दौरों की संख्या केवल log n की तरह बढ़ती है, जो मोटे तौर पर यह है कि n को कितनी बार आधा किया जा सकता है। पर एक अकेला बदलाव ग्राफ़ के एक स्थिर अंश को छू सकता है: हर एक की क़ीमत पूरे ग्राफ़ से एक बार गुज़रना है, कुल मिलाकर n log n।

पूरे ग्राफ़ से गुज़रने की जगह एक तालिका

नया शोधपत्र log n बदलाव बनाए रखता है, पर हर एक को सस्ता कर देता है। n के अनुपाती समय की एक तैयारी के बाद, हर बदलाव औसतन लगभग n / log n क़दमों में ढूँढ़ा और लागू किया जाता है। तब log n बदलाव मिलकर n के अनुपाती समय लेते हैं — रैखिक समय — एक सीमा जिसे लेखक इष्टतम कहते हैं।

तरकीब है “चार रूसियों की विधि” (Method of Four Russians)। जो उप-समस्या ½ log n बिट के एक कोड में समा जाए — यानी n को लिखने के लिए ज़रूरी द्विआधारी अंकों का आधा — उसके अधिकतम √n संभव रूप होते हैं, इसलिए उन सबके उत्तर पहले से गणना करके एक तालिका में रखे जा सकते हैं। माना गया कंप्यूटर, जिसके मेमोरी-शब्द लगभग log n बिट के हैं, कोई भी संग्रहीत उत्तर एक क़दम में पढ़ लेता है।

ग्राफ़ को बार-बार छोटी सीमाओं वाले नेस्टेड (एक-दूसरे के भीतर बसे) क्षेत्रों में काटा जाता है। सबसे छोटे क्षेत्रों में लगभग log n शीर्ष होते हैं और वे, रंगों समेत, एक कोड में समा जाते हैं। हर क्षेत्र के लिए एक छोटा सारांश-ग्राफ़ दर्ज करता है कि कौन-से सीमा-शीर्ष एक ही केम्पे शृंखला साझा करते हैं। तब एक बदलाव “बदलो” या “रखो” बिटों की लड़ियों के रूप में नीचे उतरता है, और हर छोटे क्षेत्र में एक बार तालिका देखने से सारे रंग अद्यतन हो जाते हैं।

चार रंगों से रंगे एक ग्राफ़ का हिस्सा। धूसर भाग एक क्षेत्र R है; मोटे काले कोर लाल-नीले और हरे-पीले जोड़ों की केम्पे शृंखलाओं के हैं। — चित्र 2, Inoue et al. (2026), arXiv:2610.39753.

उसी क्षेत्र का सारांश: हर नीला धब्बा केम्पे शृंखला के एक टुकड़े का प्रतिनिधित्व करता है, और उसकी रेखाएँ दिखाती हैं कि वह किन सीमा-शीर्षों को जोड़ता है। — चित्र 3, Inoue et al. (2026), arXiv:2610.39753.

बिना पासे के चुनना

यादृच्छिक चुनावों के साथ यह विधि पहले ही किसी नक़्शे को औसतन रैखिक समय में रंग देती है। गति खोए बिना पासे को हटाना “निस्संदेह सबसे चुनौतीपूर्ण हिस्सा” था। किसी वलय को तब तक जीवित कहिए जब तक अब तक का हर निर्णय उसके पक्ष में गया हो। अगर उसे छूने वाली u अनिर्णीत शृंखलाएँ सिक्का उछालने पर छोड़ दी जाएँ, तो वह 1/2^u प्रायिकता से बचेगा; सभी जीवित वलयों पर जोड़ने पर ये संख्याएँ बचने वालों की अपेक्षित संख्या देती हैं। किसी शृंखला का निर्णय उस विकल्प को चाहने वाले हर वलय के पद को दोगुना कर देता है और बाक़ियों के पद शून्य कर देता है। एल्गोरिद्म वह विकल्प चुनता है जो योग को गिरने न दे, ताकि अंत में कम से कम उतने वलयों को मदद मिले जितनों को संयोग से औसतन मिलती।

एक सीमा, स्टॉपवॉच नहीं

शोधपत्र कोई कार्यान्वयन (implementation) या चलने का समय नहीं बताता, और “n के अनुपाती” में छिपे स्थिरांक नहीं दिए गए। वे बड़े हैं: 8,202 पैटर्नों में से हर एक के लिए एल्गोरिद्म यह संग्रहीत करता है कि उसके वलय की हर रंगाई को कितने सुधारक बदलाव चाहिए — “सूचना की एक विशाल स्थिर मात्रा”। एक परिशिष्ट में वे नेस्टेड क्षेत्रों के उस 2013 के निर्माण में “एक छोटी ग़लती” भी ठीक करते हैं, जिस पर उनका काम टिका है। 1852 का एक अनुमान अब एक रंगाई-प्रक्रिया के साथ आता है जिसकी लागत उस नक़्शे से तेज़ नहीं बढ़ती जिसे वह रंगती है।