AIが1990年代の彩色予想を沈める

線で結ばれた点のネットワーク、つまりグラフを考えよう。全彩色(total colouring)とは、すべての点とすべての線に色を与えることで、3つの規則に従う。隣り合う2つの点は異なる色、1つの点で出会う2本の線は異なる色、そして線はその両端の2点と異なる色にする。これがうまくいく最小の色数を全彩色数と呼び、χ″(G)と書く。

ここで難しくしてみよう。すべての点とすべての線に、使ってよい色の専用リストを与える。リストはすべて同じ大きさkとし、リストから選んだ色で正しく塗り分けることを求める。どんなリストに対してもうまくいく最小のkがリスト全彩色数、χ″ℓ(G)である。これがχ″(G)より小さくなることはない。すべてのリストが同じなら、ふつうの問題に戻るからだ。

1990年代後半の予想

1990年代後半、3つのグループ、すなわちボロディン、コストチカ、ウッドール、ユヴァン、モハル、シュクレコフスキ、そしてヒルトンとジョンソンが、それぞれ独立に、専用のリストは決して代償を伴わないと提唱した。

すべてのグラフ(2点間に複数の線がある場合も含む)について χ″ℓ(G) = χ″(G)。

これがリスト全彩色予想である。これを裏づける証拠もあった。どの点からも線が2本以下しか出ていないグラフでは成り立つし、すべての点からちょうど3本の線が出ているグラフ(3正則グラフ、cubic graph)は、リストから最大5色で塗れることが知られていた。

反例

カナダのビクトリア大学のジョナサン・ノエル(Jonathan Noel)は、χ″ = 4 なのに χ″ℓ = 5 となる、20個の点からなる3正則グラフを示した。予想は偽である。

構成はコンパクトだ。K₂,₃と呼ばれる小さなグラフを4つ用意する。これは2つの「私的な」点が、それぞれ同じ3つの「端子」の点に結ばれたものだ。次に、それぞれのコピーの組を、端子同士を結ぶちょうど1本の「交差」線でつなぐ。すると、どの点からも3本の線が出ることになる。

わずか4色で全彩色したグラフG。色は図形と線の種類で示している。— 図1、Noel (2026), arXiv:2609.38417.

ふつうのゲームなら4色で足りる。色4をすべての私的な点とすべての交差線に割り当てる(これらは互いに決して接しない)。残りは小さな表と巡回的な規則で処理できる。

満たせないリスト

罠には1から5までの色を使う。ブロックiのすべての点と線には「i以外のすべての色」というリストを与える。交差線には、5またはi + 2が欠けた、注意深く選んだリストを与える。すると証明は、短い推理小説のように進む。

• 補題:K₂,₃をどう4色で塗っても、2つの私的な点は同じ色にならなければならない。
• したがって各ブロックiには色の組{i, sᵢ}があり、2つのブロックを結ぶ交差線はどれも、両方の組に共通する色を使わなければならない。
• ちょっとした数え上げで、ある1つの色tが4つの組すべてに属さなければならないことがわかる。
• ところが、どのtについても、特定の1本の交差線のリストにはその色が欠けている。矛盾である。

リストの割り当て。各点と各線は、1から5までの色のうち示された1色を除くすべてを使える。これらのリストを守る全彩色は存在しない。— 図2、Noel (2026), arXiv:2609.38417.

機械が見つけ、数学者が確かめた

この論文は、その出自について異例なほど率直だ。2026年9月24日、ノエルはChatGPT 6 Astra Ultraに予想の反証を促し、AIは「著者からの入力はほとんどないまま」反例を生み出した。ノエルは論証を検証し、モデルが生成した草稿をもとに文章を書き直した。モデルは校正も手伝い、参考文献を提案し、図も描いた。宣言は「正しさについては著者が全責任を負う」と締めくくられている。論文はプレプリントだが、証明は短く、根気のある読者なら誰でも検証できる。

差は1色か、それ以上か

専用のリストは余分な色を1色必要とすることがある。では、それ以上必要とすることはあるのか。差が3色になれば、よく研究されている近縁の予想、リスト辺彩色予想も崩れることになる。χ″ℓ ≤ χ′ℓ + 2 かつ χ″ ≥ χ′ だからだ。ノエルは、AIの反例でも決着しない未解決の問いで論文を締めくくっている。すべてのグラフについて χ″ℓ(G) ≤ χ″(G) + 1 は成り立つのだろうか。