அண்டை நாடுகள் எப்போதும் வேறுபட்ட நிறத்தில் இருக்க, எந்த வரைபடத்துக்கும் நான்கு நிறங்கள் போதும். இது 1976-இல் நிறுவப்பட்டது. ஆனால் நிறங்களை உண்மையில் எப்படிக் கண்டுபிடிப்பது?
மரபான கருவி கெம்ப் சங்கிலி (Kempe chain). இரண்டு நிறங்களைத் தேர்ந்தெடுத்து, அந்த இரண்டில் மட்டுமே நிறமிடப்பட்ட நாடுகளின் இணைந்த முழுப் பகுதியையும் எடுங்கள். அந்தப் பகுதி முழுவதும் அவற்றை இடம் மாற்றுங்கள்: வரைபடம் சரியாக நிறமிடப்பட்டதாகவே இருக்கிறது.
சிக்கல்: ஒரே ஓர் இடமாற்றம் வரைபடம் முழுவதும் அலையாகப் பரவக்கூடும். முந்தைய சாதனைக்கு, வரைபடங்கள் பெரிதாகும்போது அதிக இடமாற்றங்கள் தேவைப்பட்டன. ஒவ்வொன்றுக்கும் வரைபடம் முழுவதையும் ஒருமுறை கடக்கும் செலவு ஆனது.
டோக்கியோ முதல் கோபன்ஹேகன் வரையிலான ஆறு கணிதவியலாளர்கள் அந்தக் கூடுதல் செலவை நீக்கியுள்ளனர். அவர்களுடைய வழிமுறை n நாடுகளை n-க்கு விகிதமான நேரத்தில் நிறமிடுகிறது. வரைபடத்தின் சிறு துண்டுகள் ஒருமுறை தீர்க்கப்பட்டு, அட்டவணைகளில் சேமிக்கப்பட்டு, பின்னர் வெறுமனே பார்த்தெடுக்கப்படுகின்றன. இந்த வேகம் உகந்தது (optimal) என்கிறார்கள் ஆசிரியர்கள்.
மூலம்: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










