যে-কোনো মানচিত্রের জন্য চারটি রং যথেষ্ট, যাতে প্রতিবেশীরা সবসময় আলাদা হয়। এটি প্রমাণিত হয় 1976 সালে। কিন্তু আসলে রংগুলো খুঁজে বের করবেন কীভাবে?
ধ্রুপদি হাতিয়ার হলো কেম্পে শিকল। দুটি রং বেছে নিন, আর শুধু সেই দুটি রঙে রাঙানো দেশগুলোর পুরো সংযুক্ত অংশটি ধরুন। পুরো অংশ জুড়ে তাদের অদলবদল করুন: মানচিত্র ঠিকঠাক রঙিনই থাকে।
সমস্যা হলো: একটি অদলবদল পুরো মানচিত্রে ছড়িয়ে পড়তে পারে। আগের রেকর্ডে মানচিত্র বড় হলে আরও বেশি অদলবদল লাগত। প্রতিটির খরচ ছিল পুরো মানচিত্রের ওপর দিয়ে একবার যাওয়া।
টোকিও থেকে কোপেনহেগেন পর্যন্ত ছয়জন গণিতবিদ সেই বাড়তি খরচ সরিয়ে দিয়েছেন। তাঁদের অ্যালগরিদম n-টি দেশকে রং করে n-এর সমানুপাতিক সময়ে। মানচিত্রের ছোট টুকরোগুলো একবার সমাধান করে সারণিতে রাখা হয়, তারপর শুধু দেখে নেওয়া হয়। লেখকেরা এই গতিকে সর্বোত্তম বলেন।
সূত্র: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










