ఏ పటానికైనా నాలుగు రంగులు, రేఖీయ కాలంలో

సమతల కాగితంపై గీసిన ఏ పటాన్నైనా పొరుగు దేశాలు ఎప్పుడూ ఒకే రంగును పంచుకోకుండా నాలుగు రంగులతో రంగులద్దవచ్చు. Francis Guthrie దీన్ని 1852లో ఊహించారు; Appel, Haken 1976లో నిరూపించారు. కానీ నాలుగు రంగులు ఉన్నాయని మాత్రమే సిద్ధాంతం చెబుతుంది. ఇచ్చిన ఒక పటానికి వాటిని ఎలా కనుక్కోవాలి? “సులభమైన జవాబు లేదు,” అని University of Tokyoకి చెందిన Yuta Inoue, జపాన్, కెనడా, స్లొవేనియా, డెన్మార్క్‌లకు చెందిన ఐదుగురు సహచరులు రాస్తారు. ఇది ఎంత చిక్కుముడిగా ఉందంటే, అనేక ప్రతిపాదిత ప్రత్యుదాహరణలకు దారితీసింది.

చుక్కలు, గీతలు, త్రిభుజాలు

ప్రతి దేశం ఒక చుక్క, అంటే శీర్షం (vertex), అవుతుంది, ప్రతి ఉమ్మడి సరిహద్దు ఒక గీత, అంటే అంచు (edge): పటం గీతలు ఒకదానినొకటి దాటకుండా గీసిన సమతల గ్రాఫ్ (planar graph) అవుతుంది. దానికి రంగులద్దడం అంటే ప్రతి శీర్షానికీ నాలుగు రంగుల్లో ఒకదాన్ని ఇవ్వడం, ప్రతి అంచు రెండు చివర్లా వేర్వేరుగా. శీర్షాల సంఖ్యను n అనండి. ప్రతి ముఖమూ త్రిభుజంగా ఉండే త్రిభుజీకరణలను (triangulations) పరిష్కరిస్తే చాలు: ఎక్కువ అంచులు రంగులద్దడాన్ని కష్టతరం మాత్రమే చేస్తాయి.

కెంపే తారుమారు

ప్రాథమిక కదలిక A. B. Kempe 1879 పత్రం నాటిది. నాలుగు రంగులను జతలుగా చేయండి, ఉదాహరణకు ఎరుపును నీలంతో, ఆకుపచ్చను పసుపుతో. కెంపే గొలుసు (Kempe chain) అంటే ఒక జతలోని రెండు రంగులను ధరించిన శీర్షాల అనుసంధానిత సమూహం. ఒక గొలుసు మొత్తం పొడవునా ఆ రెండు రంగులను తారుమారు చేస్తే రంగులద్దడం చెల్లుబాటుగానే ఉంటుంది.

నాలుగు పొరుగు శీర్షాలు ఉన్న ఒక శీర్షం vని తీసుకోండి, దాని చుట్టూ క్రమంలో v0 నుంచి v3 వరకు, మిగతావాటికి ముందు రంగులద్దండి. పొరుగువి మూడు లేదా అంతకంటే తక్కువ రంగులు వాడితే, v ఖాళీగా ఉన్న రంగును తీసుకుంటుంది. అవి నాలుగు రంగులూ వాడితే, v0 వద్ద మొదలై v0, v2 రంగుల్లో ఉన్న గొలుసును అనుసరించండి. అది v2ని చేరకపోతే, దాన్ని తారుమారు చేయండి: v0 v2 రంగును తీసుకుంటుంది, vకి ఒక రంగు ఖాళీ అవుతుంది. అది v2ని చేరితే, దానికి బదులు v1, v3 రంగుల్లో ఉన్న v1 గొలుసును తారుమారు చేయండి, తద్వారా v1 v3 రంగును తీసుకుంటుంది.

ఎప్పుడూ బాగుచేయగలిగే ముక్కలు

సిద్ధాంత నిరూపణలు క్షయీకరణీయ విన్యాసాలపై (reducible configurations) ఆధారపడతాయి: కత్తిరించి తీసేసి, మిగతాదానికి రంగులద్దిన తర్వాత తిరిగి పెట్టగలిగే చిన్న నమూనాలు. వాటి వలయం (ring) — వాటి చుట్టూ ఉన్న శీర్షాలు — రంగులు సరిపోకపోతే, బయట చేసే పరిమిత సంఖ్యలో మెరుగుపరిచే కెంపే మార్పులు వాటిని ఎప్పుడూ సరిచేస్తాయి: ఇక్కడ వాడిన నమూనాలకు గరిష్ఠంగా 25, వాటి వలయాల్లో గరిష్ఠంగా 18 శీర్షాలు ఉంటాయి.

ఒక క్షయీకరణీయ విన్యాసం (ఎడమ; ప్రతి సంఖ్య పూర్తి పటంలో ఆ శీర్షానికి ఎన్ని పొరుగువి ఉండాలో చెబుతుంది), దాని వలయం Rతో పూర్తిచేసిన అదే నమూనా (కుడి). — Figure 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 కి అనుపాతమైన కాలం — రేఖీయ కాలం (linear time) — తీసుకుంటాయి; రచయితలు ఈ హద్దును ఇష్టతమం (optimal) అంటారు.

ఉపాయం “Method of Four Russians” (నలుగురు రష్యన్ల పద్ధతి). ½ log n బిట్ల కోడ్‌లో — n ని రాయడానికి కావాల్సిన ద్వియాంశ అంకెల్లో సగం — సరిపోయే ఉప-సమస్యకు గరిష్ఠంగా √n సాధ్యమైన రూపాలు ఉంటాయి, కాబట్టి వాటి అన్ని జవాబులనూ ముందుగానే లెక్కించి ఒక పట్టికలో భద్రపరచవచ్చు. సుమారు log n బిట్ల మెమరీ పదాలు ఉన్నట్టు భావించిన కంప్యూటర్, భద్రపరిచిన ఏ జవాబునైనా ఒకే అడుగులో చదువుతుంది.

గ్రాఫ్‌ను మళ్ళీ మళ్ళీ, చిన్న సరిహద్దులున్న, ఒకదానిలో ఒకటి ఇమిడిన ప్రాంతాలుగా కోస్తారు. అతిచిన్నవాటిలో సుమారు log n శీర్షాలు ఉంటాయి, రంగులతో సహా ఒకే కోడ్‌లో సరిపోతాయి. ప్రతి ప్రాంతానికీ, ఏ సరిహద్దు శీర్షాలు ఒకే కెంపే గొలుసును పంచుకుంటాయో ఒక చిన్న సారాంశ గ్రాఫ్ నమోదు చేస్తుంది. అప్పుడు ఒక మార్పు “తారుమారు” లేదా “అలాగే ఉంచు” బిట్ల వరుసలుగా కిందికి ప్రయాణిస్తుంది, ప్రతి చిన్న ప్రాంతంలో ఒకే చూపు ప్రతి రంగునూ నవీకరిస్తుంది.

నాలుగు రంగులతో రంగులద్దిన గ్రాఫ్‌లో ఒక భాగం. బూడిదరంగు ప్రదేశం ఒక ప్రాంతం R; మందమైన నల్లని అంచులు ఎరుపు-నీలం, ఆకుపచ్చ-పసుపు జతల కెంపే గొలుసులకు చెందినవి. — Figure 2, Inoue et al. (2026), arXiv:2610.39753.

అదే ప్రాంతం సారాంశం: ప్రతి నీలి మచ్చ కెంపే గొలుసులోని ఒక ముక్కను సూచిస్తుంది, దాని గీతలు అది ఏ సరిహద్దు శీర్షాలను కలుపుతుందో చూపిస్తాయి. — Figure 3, Inoue et al. (2026), arXiv:2610.39753.

పాచికలు లేకుండా ఎంచుకోవడం

యాదృచ్ఛిక ఎంపికలతో, ఇది ఇప్పటికే సగటున రేఖీయ కాలంలో పటానికి రంగులద్దుతుంది. వేగం కోల్పోకుండా పాచికలను తొలగించడం “అన్నింటికంటే అత్యంత సవాలైన భాగం”. ఇప్పటివరకు ప్రతి నిర్ణయమూ ఒక వలయానికి అనుకూలంగా జరిగినంతకాలం దాన్ని సజీవం అనండి. దాన్ని తాకే నిర్ణయించని u గొలుసులను బొమ్మా-బొరుసుకు వదిలేస్తే, అది 1/2^u సంభావ్యతతో బతుకుతుంది; సజీవ వలయాలన్నింటిపై కూడితే, ఈ సంఖ్యలు బతికేవాటి అంచనా సంఖ్యను ఇస్తాయి. ఒక గొలుసు గురించి నిర్ణయించడం ఆ ఎంపికను కోరిన ప్రతి వలయం పదాన్ని రెట్టింపు చేస్తుంది, మిగతావాటిని సున్నా చేస్తుంది. అల్గారిథమ్ ఆ మొత్తం తగ్గకుండా ఉంచే ఎంపికను తీసుకుంటుంది, తద్వారా చివరికి అదృష్టం సగటున ఎన్ని వలయాలకు సహాయపడేదో కనీసం అన్నింటికి సహాయం అందుతుంది.

ఒక హద్దు, స్టాప్‌వాచ్ కాదు

పత్రం ఏ అమలునూ (implementation), ఏ నడక సమయాన్నీ నివేదించదు, “n కి అనుపాతం”లో దాగిన స్థిరాంకాలను ఇవ్వదు. అవి పెద్దవి: 8,202 నమూనాల్లో ప్రతి దానికీ, దాని వలయం ప్రతి రంగులద్దకానికీ ఎన్ని మెరుగుపరిచే మార్పులు కావాలో అల్గారిథమ్ భద్రపరుస్తుంది — “భారీ స్థిర పరిమాణంలో సమాచారం”. ఒక అనుబంధంలో, తాము ఆధారపడే, ఒకదానిలో ఒకటి ఇమిడిన ప్రాంతాల 2013 నాటి నిర్మాణంలోని “ఒక చిన్న పొరపాటు”ను కూడా వారు సరిచేస్తారు. 1852 నాటి ఒక ఊహకు ఇప్పుడు, తాను రంగులద్దే పటం కంటే వేగంగా ఖర్చు పెరగని రంగులద్దే విధానం తోడైంది.