どんな地図も4色で、線形時間で塗り分ける

平らな紙の上に描かれたどんな地図も、隣り合う国どうしが決して同じ色にならないように、4色で塗り分けることができる。Francis Guthrieが1852年に予想し、AppelとHakenが1976年に証明した。しかし、この定理が述べているのは、4色による塗り分けが存在するということだけだ。与えられた地図について、それをどうやって見つければよいのか。「簡単な答えはない」と、東京大学のYuta Inoueと、日本、カナダ、スロベニア、デンマークの5人の共同研究者は書いている。この問題はあまりに込み入っていたため、反例と称するものが数多く提出されたほどだった。

点と線と三角形

それぞれの国を点、つまり頂点に置き換え、共有する国境を線、つまり辺に置き換える。すると地図は、線が交差しないように描かれた平面グラフになる。これを塗り分けるとは、各頂点に4色のうち1色を割り当て、各辺の両端が異なる色になるようにすることだ。頂点の数をnとする。すべての面が三角形になっている三角形分割（triangulation）だけを扱えば十分である。辺が多いほど、塗り分けは難しくなるだけだからだ。

ケンペの入れ替え

基本となる操作は、A. B. Kempeの1879年の論文にさかのぼる。4色を2色ずつ組にする。たとえば赤と青、緑と黄だ。ケンペ鎖とは、1つの組の2色で塗られた頂点がつながった集まりのことである。鎖全体にわたってその2色を入れ替えても、塗り分けは正しいままだ。

4つの隣接頂点をもつ頂点vを考え、そのまわりに順にv0からv3まで並んでいるとする。まず、v以外を塗っておく。隣接頂点が3色以下しか使っていなければ、vは空いている色をとればよい。4色すべてを使っていれば、v0から始まる、v0とv2の色からなる鎖をたどる。それがv2に届かなければ、その鎖で色を入れ替える。するとv0はv2の色になり、vのために1色が空く。v2に届いてしまう場合は、代わりにv1から始まる、v1とv3の色からなる鎖で入れ替えを行い、v1をv3の色にする。

いつでも修復できる断片

この定理の証明は、可約配置（reducible configuration）に基づいている。これは、切り取っておき、残りを塗り終えてから元に戻すことのできる小さなパターンである。そのまわりを囲む頂点からなる環（ring）の色がうまく合わなくても、外側で行う改善的なケンペ変更を有限回行えば、必ず修復できる。ここで使われるパターンでは、その回数は最大25回で、環の頂点は最大18個である。

可約配置（左。各数字は、地図全体の中でその頂点がもつべき隣接頂点の数）と、同じパターンをその環Rで補ったもの（右）。— Figure 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson、Sanders、Seymour、Thomasは1997年に、この方法でパターンを1つずつ処理しながら塗り分ける方法を示した。1回ごとにグラフは数個の頂点だけ小さくなり、そのたびにグラフ全体をひと通り調べる手間がかかる。そのため、所要時間は2乗のオーダーになる。地図が2倍の大きさになれば、4倍の時間がかかるということだ。

以前の論文（FOCS’26）で、同じ6人の著者は、どんな三角形分割にも、8,202個のパターンからなるリストから選んだ互いに接しない可約配置が、nに比例する個数だけ含まれていることを証明した。あるいは、両側に頂点をもつ短いループがそれだけの個数含まれていて、これも役に立つ。彼らはすべてのパターンを一度に取り除き、残りを塗り分けてから、すべての環をまとめて修復する。ランダムなケンペ変更が特定の環の役に立つのは、色の組み合わせを正しく選び（3回に1回）、その環に触れるすべての鎖でコイン投げが正しい結果になったとき（それぞれ2回に1回）である。そうした鎖が最大18本あるので、確率は少なくとも3 × 2¹⁸、つまり786,432分の1になる。小さいが、一定の値だ。そのため、必要な回数はlog n、おおよそnを半分にしていける回数に比例してしか増えない。しかし、1回の変更がグラフの一定の割合にかかわることもありうる。1回ごとに全体をひと通り調べる手間がかかるので、合計ではn log nになる。

全体を調べる代わりに表を引く

新しい論文は、log n回の変更はそのままに、1回ごとの手間を小さくした。nに比例する時間の準備をしておけば、各変更は平均して約n / log nステップで見つけて実行できる。するとlog n回の変更を合わせても、かかる時間はnに比例する。つまり線形時間であり、著者らはこれを最適な上限だとしている。

鍵となるのは「4人のロシア人の方法」（Method of Four Russians）だ。½ log nビット、つまりnを書くのに必要な2進数の桁数の半分に収まる部分問題は、ありうるパターンが最大で√n通りしかない。そのため、それらすべての答えを前もって計算し、表に保存しておける。想定するコンピュータは約log nビットのメモリワードをもち、保存された答えをどれでも1ステップで読み出せる。

グラフは、境界の短い入れ子状の領域に、何度も繰り返し切り分けられる。最も小さい領域は約log n個の頂点を含み、色も含めて1つのコードに収まる。各領域について、小さな要約グラフが、境界上のどの頂点が同じケンペ鎖に属するかを記録する。そうすると、1回の変更は「入れ替える」か「そのままにする」かを表すビット列として下へ伝わっていき、それぞれの小さな領域では、1回の表引きですべての色が更新される。

4色で塗り分けられたグラフの一部。灰色の部分が領域Rで、太い黒の辺は赤–青と緑–黄の組のケンペ鎖に属する。— Figure 2, Inoue et al. (2026), arXiv:2610.39753.

同じ領域の要約。青い塊はそれぞれケンペ鎖の一部を表し、その線は、塊がどの境界頂点どうしを結んでいるかを示している。— Figure 3, Inoue et al. (2026), arXiv:2610.39753.

サイコロを振らずに選ぶ

ランダムな選択を使えば、これだけですでに、平均して線形時間で地図を塗り分けられる。速さを失わずにサイコロを取り除くことは、「群を抜いて最も困難な部分」だった。これまでのすべての決定がその環にとって都合のよいほうに転んでいるあいだ、その環を「生きている」と呼ぶことにする。その環に触れる未決定の鎖u本をコイン投げにまかせたとすると、環が生き残る確率は1/2^uになる。生きているすべての環についてこの数を足し合わせると、生き残る環の個数の期待値が得られる。ある鎖について決定を下すと、その選択を望んでいた各環の項は2倍になり、それ以外の環の項はゼロになる。アルゴリズムは、この和が減らないほうの選択肢をとる。こうして最終的には、偶然にまかせた場合に平均して改善されるのと少なくとも同じ数の環が改善される。

ストップウォッチではなく、上限

論文は実装も実行時間も報告しておらず、「nに比例する」の中に隠れている定数も示していない。その定数は大きい。8,202個のパターンそれぞれについて、アルゴリズムは、その環のあらゆる塗り分けが何回の改善的な変更を必要とするかを保存している。「膨大な定数量の情報」である。著者らは付録で、自分たちが土台にしている2013年の入れ子状の領域の構成にあった「小さな誤り」も修正している。1852年の予想には、いまや、塗り分ける地図の大きさより速くはコストが増えない塗り分けの手順が備わったのである。