Hadwiger予想
概要
Hadwiger予想（Hadwiger's conjecture）とは、どの整数 $t\ge1$ についても、完全グラフ $K_t$ をマイナーとして含まない有限グラフは $t-1$ 色で塗り分けられる、すなわち彩色数が $t$ 以上のグラフは $K_t$ をマイナーとして含む、という 1943 年の予想である。$t\le4$ では初等的に証明でき、$t=5$ の場合は $K_5$ をマイナーとして含まないグラフについての Wagner の構造定理を通じて四色定理と同値になり、$t=6$ の場合は Robertson・Seymour・Thomas が四色定理を使って証明した。$t\ge7$ では未解決で、一般の $t$ では $K_t$ をマイナーとして含まないグラフが $O(t\log\log t)$ 色で塗れることが知られている。
前提知識: 彩色数, グラフマイナー, 完全グラフ, 四色定理, Kuratowskiの定理
グラフの頂点を、辺で結ばれた 2 頂点が違う色になるように塗るとき、必要な色の数の最小値が彩色数 $\chi(G)$ である。$t$ 色以上を要するグラフは、$t$ 個の頂点がどの 2 つも隣り合う完全グラフ $K_t$ を部分グラフとして含むとは限らない。三角形を含まず彩色数がいくらでも大きいグラフがあるからである（彩色数 の記事の注意「三角形を含まないグラフの彩色数」）。H. Hadwiger は 1943 年に、部分グラフの代わりにグラフマイナーを使えば $K_t$ が必ず現れると予想した。すなわち Hadwiger 予想 は、どの整数 $t\ge1$ についても、$K_t$ をマイナーとして含まないグラフは $t-1$ 色で塗り分けられる、という主張である（Die25 p. 189）。
$t\le4$ では初等的に証明でき、$t=5$ の場合は K. Wagner の構造定理を通じて四色定理と同値になる。$t=6$ の場合は N. Robertson・P. Seymour・R. Thomas が四色定理を使って 1993 年に証明した。$t\ge7$ では未解決である（同書 pp. 189–191）。この記事では、$t\le4$ の証明、$t=5$ と四色定理の同値性の証明（構造定理は引用する）、彩色数が $2^{t-2}$ 以下であるという一般の評価の証明を述べ、$t=6$ と一般の場合に知られていることを所在とともに述べる。平面の点の塗り分けについての Hadwiger–Nelson 問題（単位距離グラフ）とは別の問題である。
定義
この記事のグラフは有限な単純グラフとする。$\lvert G\rvert$ は頂点の個数、$e(G)$ は辺の本数、$N(x)$ は頂点 $x$ に隣接する頂点の集合である。彩色・$k$-彩色可能・彩色数 $\chi(G)$ は 彩色数 の記事の定義「頂点彩色の最小色数」に従う（頂点のないグラフは $0$-彩色可能とする）。マイナー $H\preceq G$ と分岐集合によるモデルは グラフマイナー の記事の定義「マイナー」「分岐集合による表示」に従い、2 つが一致することを使う（同記事の命題「2 つの定義の一致」）。
整数 $t\ge1$ について、次の主張を $\mathrm H(t)$ と書く。
$\mathrm H(t)$：$K_t$ をマイナーとして含まないグラフは、すべて $(t-1)$-彩色可能である。
すべての $t\ge1$ について $\mathrm H(t)$ が成り立つ、という予想を Hadwiger 予想（Hadwiger's conjecture）という。
$\mathrm H(t)$ は「$\chi(G)\ge t$ なら $K_t\preceq G$」と同じである。頂点を 1 個以上もつグラフ $G$ について、$K_t\preceq G$ となる最大の $t$ を $G$ の Hadwiger 数 といい $h(G)$ と書くと、Hadwiger 予想は「頂点を 1 個以上もつすべてのグラフについて $\chi(G)\le h(G)$」と言い換えられる。実際、予想が正しく $\chi(G)=k\ge1$ なら、$G$ は $(k-1)$-彩色可能でないので $\mathrm H(k)$ により $K_k\preceq G$ で、$h(G)\ge k$ である。逆に $\chi\le h$ がいつも成り立てば、$K_t$ をマイナーとして含まないグラフは $h(G)\le t-1$ なので $\chi(G)\le t-1$ である。
- 外周が 5 頂点の閉路で、中心の頂点がすべての外周の頂点と隣接する車輪グラフ $W_5$ では、外周は奇閉路なので 3 色を要し、中心はそのすべてと隣接するので $\chi(W_5)=4$ である。外周の隣り合わない 2 本の辺を縮約すると外周は三角形になり、中心と合わせて $K_4$ が得られる。よって $K_4\preceq W_5$ で、$\mathrm H(4)$ の主張と合っている。
- Petersenグラフ $P$ は $\chi(P)=3$ で（彩色数 の記事の例「Petersen グラフの彩色数」）、$K_5$ をマイナーとして含む（平面グラフ の記事の注意「細分を持つこととマイナーとして持つことの違い」）。$h(P)\ge5>\chi(P)$ であり、Hadwiger 数は彩色数よりずっと大きくなりうる。
基本的な補題
グラフ $G$ が 2 つの誘導部分グラフ $G_1,G_2$ の和 $G=G_1\cup G_2$ で、$G_1\cap G_2$ が完全グラフ（頂点がなくてもよい）であるとする。このとき $\chi(G)=\max\{\chi(G_1),\chi(G_2)\}$ である。
$\ge$ は部分グラフの彩色数が増えないことによる（彩色数 の記事の命題「部分グラフと連結成分」）。$k:=\max\chi(G_i)$ とし、$G_i$ の $k$-頂点彩色 $c_i$ をとる。$S:=V(G_1\cap G_2)$ の頂点はどの 2 つも隣接するので、$c_1,c_2$ はどちらも $S$ の上で単射である。そこで $\{1,\dots,k\}$ の置換 $\pi$ で、$S$ の上で $\pi\circ c_2=c_1$ となるものがとれる。$V(G_1)$ では $c_1$、$V(G_2)$ では $\pi\circ c_2$ を使う写像 $c$ は $S$ の上で矛盾なく定まる。$G$ のどの辺も $G_1$ か $G_2$ の辺なので、$c$ は $G$ の $k$-頂点彩色である。$\square$
$G$ が $G_1$ と $G_2$ を $G_1\cap G_2$ に沿って 貼り合わせた グラフである、ともいう（Die25 p. 140）。
グラフ $G$ に新しい頂点 $v$ を加え、$v$ を $G$ のすべての頂点と結んだグラフを $G\ast v$ とする。$G\ast v$ が $K_{t+1}$ をマイナーとして含めば、$G$ は $K_t$ をマイナーとして含む。
$G\ast v$ の中の $K_{t+1}$ のモデル $(V_1,\dots,V_{t+1})$ をとる。$v$ を含む $V_i$ は高々 1 つなので、それ（なければ $V_{t+1}$）を除く。残りの $t$ 個は $v$ を含まないので、$G$ の中で連結な部分グラフを誘導し、その間を結ぶ辺は $v$ に接続しないので $G$ の辺である。よって $G$ の中の $K_t$ のモデルである。$\square$
$\mathrm H(t+1)$ が成り立てば $\mathrm H(t)$ も成り立つ。
$G$ が $K_t$ をマイナーとして含まなければ、lem-hc-apex により $G\ast v$ は $K_{t+1}$ をマイナーとして含まないので、$\mathrm H(t+1)$ により $t$-頂点彩色をもつ。$v$ はすべての頂点と隣接するので、$v$ の色は $G$ のどの頂点にも使われず、$G$ には $t-1$ 色しか使われない。$\square$
これは Die25 の演習 27（p. 221）である。とくに、ある $t_0$ で $\mathrm H(t_0)$ が示されれば、$t\le t_0$ のすべてで成り立つ。
$G$ を連結で切断点をもたないグラフとし、$V(G)=V_1\cup V_2$、$V_1\cap V_2=\{u,v\}$（$u\ne v$）、$V_1\setminus V_2$ と $V_2\setminus V_1$ はともに空でなく、その間を結ぶ辺はないとする。このとき、$G[V_1]$ に辺 $uv$ を加えたグラフ $G[V_1]+uv$ は $G$ のマイナーである。
$b\in V_2\setminus V_1$ を含む $G-\{u,v\}$ の連結成分を $D$ とすると、$D\subset V_2\setminus V_1$ である。$G-u$ は連結なので、$D$ の頂点から $V_1\setminus V_2$ の頂点への道が $G-u$ の中にあり、それは $D$ の外へ出るところで $v$ を通る（$D$ の頂点の隣接頂点は $D\cup\{u,v\}$ にある）。よって $v$ は $D$ に隣接頂点をもち、同様に $u$ ももつ。したがって、内部の頂点がすべて $D$ に属する $u$ から $v$ への道 $P$ がある。$G[V_1]\cup P$ は $G$ の部分グラフであり、$P$ の辺を 1 本だけ残して縮約すると $G[V_1]+uv$ になる。$\square$
$t\le4$ の場合
$\mathrm H(1)$、$\mathrm H(2)$、$\mathrm H(3)$ は成り立つ。
$t=4$ の場合には、3-連結グラフが $K_4$ をマイナーとして含むことを使う。グラフ $G$ が 3-連結 であるとは、$\lvert G\rvert\ge4$ で、どの 2 個以下の頂点を除いても連結のままであることをいう（連結度(グラフ)）。
3-連結グラフは $K_4$ の細分を部分グラフとして含む。とくに $K_4$ をマイナーとして含む。
要点：最長の道の端点から長さ $4$ 以上の閉路 $C$ を作り、$C$ の 2 つの弧を結ぶ道を 2 回とる。2 本の道が交わらなければ $C$ と 2 本の道が、交われば最初の交点までの部分が $K_4$ の細分を与える。
詳しい証明を開く
次数 $2$ 以下の頂点 $x$ があれば、$\lvert G\rvert\ge4$ なので $N(x)$ を除くと $x$ が残りから切り離され、3-連結性に反する。よって最小次数は $3$ 以上である。最長の道 $x_0x_1\cdots x_k$ をとると、$x_0$ の隣接頂点はすべてこの道の上にあり（そうでなければ道を延ばせる）、3 個以上あるので $j\ge3$ の $x_j$ がある。閉路 $C:=x_0x_1\cdots x_jx_0$ の長さは $4$ 以上である。
$C$ の上で隣り合わない 2 頂点 $u,v$ をとると、$C-\{u,v\}$ は空でない 2 つの弧 $R_1,R_2$ に分かれる。$G-\{u,v\}$ は連結なので $R_1$ から $R_2$ への道があり、その部分道で、端点 $x\in R_1$、$y\in R_2$ 以外は $C$ と交わらないもの $P$ がとれる。$C$ の上で $u,x,v,y$ はこの巡回順に並ぶので、$x,y$ は $C$ の上で隣り合わず、$C-\{x,y\}$ は $u$ を含む弧 $S_1$ と $v$ を含む弧 $S_2$ に分かれる。同様に $G-\{x,y\}$ の中に、端点 $u'\in S_1$、$v'\in S_2$ 以外は $C$ と交わらない道 $Q$ がとれる。
$P$ と $Q$ が共有する頂点がなければ、$C$ の上の巡回順は $x,u',y,v'$ で、$x,u',y,v'$ を分岐点とし、$C$ をこの 4 点で切った 4 本の弧と $P$、$Q$ を道とすれば $K_4$ の細分になる。共有する頂点があれば（それは $P$ と $Q$ の内部の頂点である）、$P$ を $x$ からたどって最初に $Q$ にのる頂点を $w$ とする。$x,u',v',w$ を分岐点とし、$C$ を $x,u',v'$ で切った 3 本の弧と、$P$ の $x$ から $w$ までの部分、$Q$ の $w$ から $u'$ までと $w$ から $v'$ までの部分を道とすれば、これらは端点以外を共有しないので $K_4$ の細分になる。細分を含めばマイナーとして含む（Kuratowskiの定理 の定義「マイナー」の後の注意）。$\square$
この証明は BM76 Theorem 8.5（pp. 123–124）の後半の議論による。
$K_4$ をマイナーとして含まないグラフは 3-彩色可能である。すなわち $\mathrm H(4)$ が成り立つ。
要点：最小の反例は、切断点も 2 頂点の分離ももたないことを貼り合わせで示せるので 3-連結になり、lem-hc-three-connected に反する。
詳しい証明を開く
反例があるとして、頂点の個数が最小の反例 $G$ をとる。$G$ は $K_4$ をマイナーとして含まず、$\chi(G)\ge4$ である。頂点が $3$ 個以下のグラフは 3-彩色可能なので $\lvert G\rvert\ge4$ である。$G$ の真の部分グラフや真のマイナーも $K_4$ をマイナーとして含まないので（マイナーのマイナーはマイナー）、頂点が少なければ 3-彩色可能である。
(a) $G$ は連結で切断点をもたない。$G$ が連結でなければ、1 つの連結成分を $G_1$、残りを $G_2$ とし、切断点 $w$ があれば、$G-w$ の 1 つの連結成分 $D$ について $G_1:=G[V(D)\cup\{w\}]$、$G_2:=G-V(D)$ とする。どちらも誘導部分グラフで、$G=G_1\cup G_2$、$G_1\cap G_2$ は空か 1 頂点（完全グラフ）であり、$G_i$ は $G$ より頂点が少ない。lem-hc-paste により $\chi(G)=\max\chi(G_i)\le3$ となって矛盾する。
(b) $G$ は 2 頂点で分離されない。2 頂点 $u,v$ で $G-\{u,v\}$ が連結でないとする。1 つの連結成分 $D$ について $V_1:=V(D)\cup\{u,v\}$、$V_2:=V(G)\setminus V(D)$ とおくと、lem-hc-two-cut の仮定が成り立つ。$G_1:=G[V_1]+uv$、$G_2:=G[V_2]+uv$ はどちらも（$V_1$ と $V_2$ の役割を入れ替えて補題を使えば）$G$ のマイナーで、頂点が少ないので 3-彩色可能である。$G+uv$ は $G_1$ と $G_2$ を辺 $uv$（完全グラフ $K_2$）に沿って貼り合わせたものなので、lem-hc-paste により $\chi(G)\le\chi(G+uv)\le3$ となって矛盾する。
(a)(b) と $\lvert G\rvert\ge4$ により $G$ は 3-連結であり、lem-hc-three-connected により $K_4$ をマイナーとして含む。これは $G$ のとり方に反する。$\square$
$t=4$ の場合は Hadwiger 自身が予想を述べた 1943 年の論文で証明した（Die25 第 7 章の注、p. 225）。G. A. Dirac は 1952 年に、彩色数が $4$ 以上のグラフは $K_4$ の細分を部分グラフとして含む、というより強い形を示した（BM76 Theorem 8.5、p. 123）。$K_4$ をマイナーとして含まず辺をもう加えられないグラフが、三角形を辺に沿って貼り合わせて作られることから導く証明もある（Die25 Proposition 7.3.1・Corollary 7.3.3、p. 190）。
$t=5$ の場合と四色定理
頂点を $\mathbb Z/8\mathbb Z$ の元 $0,1,\dots,7$ とし、$i$ と $i\pm1$、$i$ と $i+4$ を結んだ 8 頂点・12 辺のグラフを Wagner グラフ といい、$W$ と書く。8 角形に、向かい合う頂点を結ぶ 4 本の対角線を加えた形である。
頂点 $0,1,\dots,7$ に順に色 $1,2,1,2,3,1,2,3$ を塗ると、隣り合う $i,i+1$（$7$ と $0$ も含む）の色の組は $(1,2),(2,1),(1,2),(2,3),(3,1),(1,2),(2,3),(3,1)$、対角線 $i,i+4$ の色の組は $(1,3),(2,1),(1,2),(2,3)$ で、どれも異なる。一方 $0,1,2,3,4$ は長さ $5$ の閉路（辺 $40$ は対角線）なので 2 色では塗れない。よって $\chi(W)=3$ である。
外側の面を含むすべての面の境界が三角形である平面グラフ図を 平面三角形分割 という（Die25 p. 100）。平面三角形分割は平面グラフである。次の構造定理は、$K_5$ をマイナーとして含まないグラフが、平面三角形分割と $W$ を小さな完全グラフに沿って貼り合わせて得られることを述べる。
$G$ は $K_5$ をマイナーとして含まず、隣接しないどの 2 頂点を結んでも $K_5$ をマイナーとして含むようになるグラフで、$\lvert G\rvert\ge4$ であるとする。このとき $G$ は、平面三角形分割と $W$ の複製から始めて、三角形または $K_2$ に沿った貼り合わせ（lem-hc-paste の形）を繰り返して作られる。
- $\mathrm H(5)$ が成り立てば、四色定理（すべての平面グラフは 4-彩色可能である）が成り立つ。
- thm-hc-wagner と四色定理から $\mathrm H(5)$ が従う。
したがって、Wagner の構造定理のもとで $\mathrm H(5)$ は四色定理と同値であり、四色定理が成り立つので $\mathrm H(5)$ も成り立つ。
1：平面グラフのマイナーは平面グラフで、$K_5$ は平面グラフでない（Kuratowskiの定理 の系「マイナーをとる操作と平面性」と 平面グラフ の記事の命題「$K_5$ は平面グラフでない」）。よって平面グラフは $K_5$ をマイナーとして含まず、$\mathrm H(5)$ により 4-彩色可能である。
2：$G$ は $K_5$ をマイナーとして含まないとする。$\lvert G\rvert\le4$ なら $\chi(G)\le4$ である。$\lvert G\rvert\ge5$ なら、同じ頂点集合の上で、$K_5$ をマイナーとして含まないまま辺を加えられるだけ加えたグラフ $G'\supset G$ をとる（辺は有限個なので操作は終わる）。thm-hc-wagner により $G'$ は貼り合わせの繰り返しで作られる。材料の平面三角形分割は平面グラフなので四色定理により $\chi\le4$、$W$ は ex-hc-wagner-color により $\chi(W)=3$ である。三角形と $K_2$ は完全グラフなので、lem-hc-paste により貼り合わせのたびに彩色数は 2 つの材料の大きいほうに等しい。貼り合わせの回数についての帰納法で $\chi(G')\le4$ であり、$G$ は $G'$ の部分グラフなので $\chi(G)\le4$ である。$\square$
2 は Die25 Corollary 7.3.6（p. 191）、1 は同書の演習 26（p. 221）である。四色定理の証明は計算機による場合分けを使う（四色定理 の注意「四色定理の証明と出典」）。$\mathrm H(5)$ を四色定理によらずに示せれば、構造定理と 1 を通じて四色定理の新しい証明が得られる。Wagner が $K_5$ をマイナーとして含まないグラフを調べたのは、四色問題を平面の位相によらずに扱うためであったが、構造定理の中に平面性が再び現れる（Die25 第 7 章の注、p. 225）。
$t=6$ の場合
$\mathrm H(6)$ が成り立つ。すなわち、$K_6$ をマイナーとして含まないグラフは 5-彩色可能である。
この定理は Robertson・Seymour・Thomas が 1993 年に証明した（Die25 Theorem 7.3.7、p. 191。原論文は同書の注、p. 225 に挙げられている）。この記事では証明しない。証明は、四色定理を使わずに、頂点の個数が最小の反例が「平面グラフに頂点を 1 つ加えたグラフ」になることを示し、最後に四色定理を使う（同書 p. 191）。最後の段は次のとおりである：$G-v$ が平面グラフなら、四色定理により $G-v$ を 4 色で塗り、$v$ に 5 色目を塗れば $\chi(G)\le5$ である。
cor-hc-monotone により $\mathrm H(6)$ から $\mathrm H(5)$ が、thm-hc-five の 1 により四色定理が従う。このため $\mathrm H(6)$ も四色定理と同値であるといわれる（Die25 p. 189）。$t\ge7$ では、$\mathrm H(t)$ は未解決である（同所）。
一般の $t$ についての評価
彩色数が $t$ 以上のグラフは辺が多い部分グラフを含み（彩色数 の記事の命題「部分グラフの最小次数による上界」の対偶）、辺が多いグラフは大きな完全グラフをマイナーとして含む。この 2 段で Hadwiger 予想の弱い形が得られる。
整数 $t\ge1$ とする。頂点を 1 個以上もつグラフ $G$ の平均次数 $2e(G)/\lvert G\rvert$ が $2^{t-2}$ 以上なら、$G$ は $K_t$ をマイナーとして含む。
要点：辺の密度 $e/\lvert\cdot\rvert$ を保つ極小なマイナーでは、隣り合う 2 頂点が多くの共通の隣接頂点をもつ（そうでなければその辺を縮約して密度を保ったまま小さくできる）。1 つの頂点の隣接頂点たちの誘導部分グラフに帰納法を使う。
詳しい証明を開く
$t$ についての帰納法で示す。$t=1$ なら $G$ は頂点をもつので $K_1\preceq G$、$t=2$ なら $e(G)\ge\lvert G\rvert/2>0$ なので辺があり $K_2\preceq G$ である。$t\ge3$ とし、$d:=2^{t-3}$（正の整数）とおくと、仮定は $e(G)\ge d\lvert G\rvert$ である。$G$ のマイナー $H$ で $\lvert H\rvert\ge1$ かつ $e(H)\ge d\lvert H\rvert$ となるもののうち、$\lvert H\rvert+e(H)$ が最小のものをとる（$G$ 自身が条件を満たす）。$\lvert H\rvert=1$ なら $e(H)=0< d$ なので $\lvert H\rvert\ge2$ である。頂点 $x\in H$ が孤立していれば、$H-x$ は $e(H-x)=e(H)\ge d\lvert H\rvert>d\lvert H-x\rvert$ を満たして最小性に反する。よって $x$ は隣接頂点 $y$ をもつ。$x,y$ の共通の隣接頂点の個数を $c$ とすると、縮約 $H/xy$ は頂点が 1 個、辺が $1+c$ 本少ない。$c\le d-1$ なら $e(H/xy)\ge e(H)-d\ge d(\lvert H\rvert-1)=d\lvert H/xy\rvert$ となって最小性に反するので、$c\ge d$ である。
したがって誘導部分グラフ $H':=H[N(x)]$（$x$ は孤立していないので頂点をもつ）の各頂点の次数は $d$ 以上で、$H'$ の平均次数は $d=2^{(t-1)-2}$ 以上である。帰納法の仮定により $H'$ は $K_{t-1}$ のモデルをもつ。$x$ は $N(x)$ のすべての頂点と隣接するので、そのモデルに分岐集合 $\{x\}$ を加えると $H$ の中の $K_t$ のモデルになり、$K_t\preceq H\preceq G$ である。$\square$
この命題と証明は Die25 Proposition 7.2.1（pp. 185–186）による。
$t\ge2$ とする。$K_t$ をマイナーとして含まないグラフ $G$ は $2^{t-2}$-彩色可能である。
$G$ の頂点を 1 個以上もつ部分グラフ $H$ も $K_t$ をマイナーとして含まないので、prop-hc-mader により平均次数は $2^{t-2}$ 未満であり、最小次数 $\delta(H)$ は平均次数以下の整数なので $\delta(H)\le2^{t-2}-1$ である。彩色数 の記事の命題「部分グラフの最小次数による上界」により $\chi(G)\le2^{t-2}$ である。$\square$
$t=2,3$ ではこれは $\mathrm H(t)$ そのものだが、$t=4$ では 4 色で、$\mathrm H(4)$ より弱い。現在知られている評価は次のとおりである（どれもこの記事では証明しない）。
- Kostochka と Thomason：定数 $c$ があり、平均次数が $c\,t\sqrt{\log t}$ 以上のグラフは $K_t$ をマイナーとして含む。この大きさは定数倍を除いて最良である（Die25 Theorem 7.2.4、p. 187 と第 7 章の注、p. 224）。cor-hc-exponential と同じ議論で、$K_t$ をマイナーとして含まないグラフは $O(t\sqrt{\log t})$ 色で塗れる。
- Delcourt と Postle：$K_t$ をマイナーとして含まないグラフは $O(t\log\log t)$ 色で塗れる（DP24 Theorem 1.5、p. 2。それ以前の Norin・Postle・Song による $O(t(\log t)^\beta)$（$\beta>1/4$）の評価は同論文の Theorem 1.4）。
- 特別なグラフの族：Hadwiger 予想は線グラフ、内周の大きいグラフ、および「ほとんどすべてのグラフ」について成り立つ（Die25 p. 189 と第 7 章の注、p. 225）。
条件を外したときの反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| マイナー（部分グラフに替える） | 閉路 $C_5$（$t=3$） | 彩色数が $t$ 以上なら $K_t$ を含むこと |
| マイナー（位相的マイナーに替える） | Catlin の例 | 彩色数が $t$ 以上なら $K_t$ の細分を含むこと |
| 色の数 $t-1$（$t-2$ に減らす） | $K_{t-1}$（$t\ge2$） | $K_t$ をマイナーとして含まなければ $t-2$ 色で塗れること |
| 主張の向き（逆にする） | 閉路 $C_4$（$t=3$） | $K_t$ をマイナーとして含めば彩色数が $t$ 以上であること |
1 行目：$C_5$ は奇閉路なので $\chi(C_5)=3$ だが、弦がないので三角形を部分グラフとして含まない。$K_3$ はマイナーとしては含む（辺を 2 本縮約する）。
2 行目：位相的マイナーに替えた主張は Hajós の予想と呼ばれ、$t\le4$ では正しい（$t=4$ は BM76 Theorem 8.5、p. 123）が、一般には正しくない。Catlin が 1979 年に反例を見つけ、ほとんどすべてのグラフで成り立たないことも知られている（Die25 p. 192 と第 7 章の注、p. 225。この記事では証明しない）。
3 行目：$K_{t-1}$ は頂点が $t-1$ 個なので $K_t$ をマイナーとして含まない（グラフマイナー の記事の命題「マイナーの順序」の 1）が、彩色数は $t-1$ である。したがって $\mathrm H(t)$ の色の数は減らせない。
4 行目：$C_4$ の辺を 1 本縮約すると $K_3$ になるが、$C_4$ は二部グラフで $\chi(C_4)=2$ である。
補足
- 予想の位置づけ：cor-hc-monotone により、$\mathrm H(t)$ は $t$ が大きいほど強い主張である。$K_t$ をマイナーとして含まないグラフの構造が十分に分かれば、その塗り分けも分かるはずだ、という見方から、$t=4$ では thm-hc-four、$t=5$ では thm-hc-wagner が使われる（Die25 p. 190）。
- マイナーの理論との関係：$K_t$ をマイナーとして含まないグラフの族はマイナー閉である（グラフマイナー の記事の命題「禁止マイナーによる特徴づけ」）。Robertson と Seymour は、この族のグラフが曲面にほぼ埋め込める部分に木分解されることを示した（Die25 pp. 403–404）。
- 四色定理との関係：$t=5$ の場合の thm-hc-five の 2 の証明と、$t=6$ の場合の Robertson・Seymour・Thomas の証明は、どちらも四色定理を使う（Die25 p. 191）。
関連項目
- 前提: 彩色数, グラフマイナー, 完全グラフ
- 比較: 四色定理, 五色定理, Kuratowskiの定理
- 例: 車輪グラフ, Petersenグラフ
- 発展: 退化数, 線グラフ
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
