どんな地図も、隣り合う国どうしが必ず違う色になるように4色で塗り分けられる。これは1976年に証明された。だが、実際にはどうやってその色を見つければよいのだろうか。
古典的な道具はケンペ鎖だ。2つの色を選び、その2色だけで塗られた国々がつながってできる領域を丸ごととる。その領域全体で2色を入れ替えても、地図は正しく塗り分けられたままだ。
難点は、たった1回の入れ替えが地図全体に波及しうることだ。これまでの最高記録では、地図が大きくなるほど多くの入れ替えが必要だった。しかも1回ごとに地図全体をひと通り調べる手間がかかった。
東京からコペンハーゲンまでの6人の数学者が、その余分な手間を取り除いた。彼らのアルゴリズムは、n個の国をnに比例する時間で塗り分ける。地図の小さな断片は一度だけ解かれて表に保存され、あとは参照するだけだ。著者らは、この速さを最適だとしている。
出典:Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










