పొరుగు దేశాలకు ఎప్పుడూ వేర్వేరు రంగులు ఉండేలా, ఏ పటానికైనా నాలుగు రంగులు సరిపోతాయి. ఇది 1976లో నిరూపితమైంది. కానీ ఆ రంగులను అసలు ఎలా కనుక్కోవాలి?
సంప్రదాయ సాధనం కెంపే గొలుసు. రెండు రంగులను ఎంచుకుని, ఆ రెండింటితో మాత్రమే రంగులద్దిన, ఒకదానికొకటి అనుసంధానమైన దేశాల ముక్క మొత్తాన్ని తీసుకోండి. ఆ ముక్క అంతటా వాటిని తారుమారు చేయండి: పటం సరిగ్గానే రంగులద్దబడి ఉంటుంది.
చిక్కేమిటంటే: ఒక్క తారుమారు పటం మొత్తం అలలా వ్యాపించగలదు. గత రికార్డుకు పటాలు పెద్దవైనకొద్దీ ఎక్కువ తారుమారులు కావాల్సి వచ్చింది. ఒక్కొక్కటీ పటం మొత్తం ఒక పూర్తి పరిశీలన ఖర్చయ్యేది.
టోక్యో నుంచి కోపెన్హాగన్ వరకు ఉన్న ఆరుగురు గణిత శాస్త్రవేత్తలు ఆ అదనపు ఖర్చును తొలగించారు. వారి అల్గారిథమ్ n దేశాలకు n కి అనుపాతంలో ఉండే కాలంలో రంగులద్దుతుంది. పటంలోని చిన్న ముక్కలను ఒక్కసారి పరిష్కరించి, పట్టికల్లో భద్రపరిచి, తర్వాత కేవలం చూసుకుంటారు. రచయితలు ఈ వేగాన్ని ఇష్టతమం (optimal) అంటారు.
మూలం: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










