未解決問題、組合せ論と離散数学、1943年に提起

ハドウィガー予想（グラフマイナー）

未解決

$K_t$ マイナーをもたない任意のループなしグラフ $G$ は $(t - 1)$ -彩色可能である。同値な表現として、彩色数が $\chi(G) \ge t$ であるすべてのグラフ $G$ は完全グラフ $K_t$ をマイナーとして含む。

研究の最前線 2026年時点

2026年現在、ハドウィガー予想は $t \le 6$ まで証明されており、 $t \ge 7$ はすべて未解決である。 $K_t$ マイナーをもたないすべてのグラフ $G$ で $\chi(G) \le C t$ が成り立つという線形ハドウィガー予想でさえ未解決のままである。コストチカ（1982年）とトマソン（1984年）による縮退度からの評価 $\chi(G) = O(t \sqrt{\log t})$ の後、ノリン、ポスル、ソン（2019/2023年）が縮退度の壁を破り、デルクールとポスル（2021年）が現在の最良の一般上界 $\chi(G) = O(t \log \log t)$ を確立した。

既知の最良の結果

ハドウィガー予想はすべての $t \le 6$ に対して正確に成り立つ（ロバートソン、シーモア、トーマス、1993年）。
$K_t$ マイナーをもたないすべてのグラフ $G$ の彩色数は $\chi(G) = O(t \log \log t)$ である（ノリン・ポスル・ソンを改良したデルクールとポスルの2021年の結果）。

使われた手法と限界

手法	達成したこと	限界
グラフマイナー構造理論とエイペックス還元	$K_6$ マイナーをもたない最小の $6$ -彩色グラフが平面グラフ上のエイペックス・グラフであることを突き止め、 $t = 6$ を四色定理へ帰着させた。	$t \ge 7$ では、 $K_t$ マイナーをもたないグラフが高種数の曲面や渦（vortex）から構成され得るため、平面グラフの彩色定理では制御できなくなる。
密な部分グラフの連結と彩色分離分解	彩色数の大きいグラフから頂点素な密で高連結な部分グラフ群を取り出して連結し $K_t$ マイナーを作ることで、 $\chi(G) = O(t \log \log t)$ を達成した。	再帰的な密度増分ステップにおいて、小規模グラフの評価と $K_t$ を構築するための分割数のバランスをとる際に $\log \log t$ の因子が失われる。

未解決の問い

$K_7$ マイナーをもたないすべてのグラフは $6$ -彩色可能か（ $t = 7$ ）。
$K_t$ マイナーをもたないすべてのグラフ $G$ が $\chi(G) \le C t$ を満たすような絶対定数 $C > 0$ が存在するか（線形ハドウィガー予想）。

参考文献

Neil Robertson, Paul Seymour, Robin Thomas (1993). Hadwiger's conjecture for K6-free graphs · DOI:10.1007/BF01202354
Sergey Norin, Luke Postle, Zi-Xia Song (2023). Breaking the degeneracy barrier for coloring graphs with no Kt minor · DOI:10.1016/j.aim.2023.108959 · arXiv:1910.09378