Hajós予想(Hajós conjecture)とは、彩色数が $k$ 以上のグラフは完全グラフ $K_k$ の細分を部分グラフとして含む、という G. Hajós の主張で、細分を含めばマイナーとして含むので Hadwiger 予想を強めたものにあたる。$k\le3$ では易しく、$k=4$ は Dirac が証明した。一方、閉路 $C_5$ の各頂点を三角形に置き換えた 15 頂点のグラフは、どの 3 頂点にも辺があるので彩色数が $8$ だが $K_8$ の細分を含まず、すべての頂点と結ぶ頂点を加えても反例は反例のままなので、予想は $k\ge8$ で成り立たない。Catlin は $k\ge7$ で反例を与え、$k=5,6$ は未解決である。
前提知識: 彩色数, Kuratowskiの定理, Hadwiger予想, 完全グラフ
Hajós予想(Hajós conjecture)は、彩色数が $k$ 以上のグラフは完全グラフ $K_k$ の細分を部分グラフとして含む、という主張である。G. Hajós の予想で、BM76 §8.3(p. 123)は Hajós の 1961 年の論文に、LW22 p. 2 は 1940 年代に帰している。$k\le3$ では易しく、$k=4$ は G. A. Dirac が 1952 年に証明した(同書 Theorem 8.5、p. 123)。しかし一般には正しくない。P. Catlin は 1979 年に $k\ge7$ のすべてで反例を与え、P. Erdős と S. Fajtlowicz はほとんどすべてのグラフで予想が成り立たないことを示した(Moh05 p. 1、Die25 第 7 章の注、p. 225)。$k=5$ と $k=6$ の場合は未解決である(LW22 p. 2)。
細分を含めばマイナーとして含むので、Hajós 予想は Hadwiger予想 を強めた主張である(Die25 p. 192)。Hadwiger 予想は $k\le6$ で証明されているのに対し、Hajós 予想は $k=8$ で具体的なグラフにより否定される。この記事では、$k\le4$ の証明、反例が $k$ を上げても反例のままであることの証明、彩色数 $8$ で $K_8$ の細分を含まないグラフ $C_5[K_3]$ についての完全な証明を述べる。グラフの彩色についての Hajós の構成(Die25 Theorem 5.2.6、p. 131)や、格子についての Hajós の定理とは別の主張である。
この記事のグラフは有限な単純グラフとする。$\lvert G\rvert$ は頂点の個数、$e(G)$ は辺の本数、$\chi(G)$ は彩色数である。細分、分岐点、分割点は Kuratowskiの定理 の定義「細分と位相的マイナー」に従い、完全グラフ $K_k$ の細分を $TK_k$ と書く。$TK_k$ は、$k$ 個の分岐点と、分岐点の 2 点ずつを結ぶ $\binom k2$ 本の道からなり、どの 2 本の道も端点以外の頂点を共有しない。分岐点はどの道の内部にも現れない。
整数 $k\ge1$ について、次の主張を $\mathrm{HJ}(k)$ と書く。
$\mathrm{HJ}(k)$:$\chi(G)\ge k$ をみたすグラフ $G$ は、$TK_k$ を部分グラフとして含む。
すべての $k\ge1$ について $\mathrm{HJ}(k)$ が成り立つ、という主張を Hajós 予想 という。
BM76 p. 123 は「$k$ 色を要するグラフは $K_k$ の細分を含む」と述べ、Die25 p. 192 は「彩色数が $r$ 以上のグラフは $K_r$ を位相的マイナーとして含む」と述べる。どちらも $\mathrm{HJ}(k)$ と同じである(彩色数が $k$ より大きいグラフは、彩色数がちょうど $k$ の部分グラフを含む。頂点を 1 つずつ除くと彩色数は $1$ ずつしか減らないからである)。
$TK_k$ を含めば $K_k$ をマイナーとして含む(Kuratowskiの定理 の定義「マイナー」の後の段落)。よって $\mathrm{HJ}(k)$ は、Hadwiger予想 の定義「Hadwiger 予想の主張」の $\mathrm H(k)$ を導く。逆は成り立たない。
$\mathrm{HJ}(1)$、$\mathrm{HJ}(2)$、$\mathrm{HJ}(3)$ は成り立つ。
$\chi(G)\ge1$ なら $G$ は頂点をもち、1 頂点が $TK_1$ である。$\chi(G)\ge2$ なら $G$ は辺をもち、1 本の辺が $TK_2$ である。$\chi(G)\ge3$ なら $G$ は 2 色で塗れないので奇閉路を含む(彩色数 の命題「2 色で彩色できるグラフ」)。閉路は $K_3$ の細分である。$\square$
$\chi(G)\ge4$ をみたすグラフ $G$ は $TK_4$ を部分グラフとして含む。すなわち $\mathrm{HJ}(4)$ が成り立つ。
証明には Hadwiger予想 の 2 つの補題を使う。補題「完全グラフに沿った貼り合わせ」は、$G$ が 2 つの誘導部分グラフ $G_1,G_2$ の和で $G_1\cap G_2$ が完全グラフ(空でもよい)なら $\chi(G)=\max\{\chi(G_1),\chi(G_2)\}$ であることを述べる。補題「3-連結グラフの中の $K_4$」は、3-連結グラフ(頂点が $4$ 個以上で、どの 2 個以下の頂点を除いても連結なグラフ)が $TK_4$ を含むことを述べる。
主張が成り立たないとして、反例のうち $\lvert G\rvert+e(G)$ が最小のもの $G$ をとる。$G$ は $TK_4$ を含まず $\chi(G)\ge4$ なので $\lvert G\rvert\ge4$ である。$G$ の部分グラフも $TK_4$ を含まないので、頂点か辺の少ない $G$ の部分グラフはどれも、最小性から彩色数が $3$ 以下である。
1. $G$ は連結で、切断点をもたない。 そうでなければ、Hadwiger予想 の定理「$t=4$ の場合」の証明の (a) と同じく、$G=G_1\cup G_2$ と、$G_1\cap G_2$ が空か 1 頂点であり $G_1,G_2$ が頂点の少ない誘導部分グラフであるものに分けられる。$\chi(G_i)\le3$ なので、補題「完全グラフに沿った貼り合わせ」から $\chi(G)\le3$ となって矛盾する。
2. $G$ は 2 頂点で分離されない。 相異なる 2 頂点 $u,v$ について $G-\{u,v\}$ が連結でないとする。その連結成分 $D$ を 1 つとり、$V_1:=V(D)\cup\{u,v\}$、$V_2:=V(G)\setminus V(D)$ とおく。$V_1\setminus V_2=V(D)$ と $V_2\setminus V_1$ はともに空でなく、その間を結ぶ辺はない。$i=1,2$ について、$G[V_i]$ に辺 $uv$ を加えたもの(すでにあればそのまま)を $G_i^+$ とする。
まず、各 $i$ について、内部の頂点がすべて $V_i\setminus V_{3-i}$ に属する $u$ から $v$ への道があることを示す。$V_i\setminus V_{3-i}$ の頂点を含む $G-\{u,v\}$ の連結成分 $D'$ をとると、$D'\subseteq V_i\setminus V_{3-i}$ である。1 により $G-v$ は連結なので、$D'$ の頂点から $V_{3-i}\setminus V_i$ の頂点への道が $G-v$ の中にある。この道が $D'$ を出るときに通る頂点は $D'$ の頂点に隣接し $D'$ の外にあるので $u$ である。よって $u$ は $D'$ に隣接頂点をもち、同様に $v$ ももつ。$D'$ は連結なので、求める道がとれる。
次に、$G+uv$ は $G_1^+$ と $G_2^+$ の和で、これらは $G+uv$ の誘導部分グラフであり、共通部分は辺 $uv$(完全グラフ $K_2$)である。両方の彩色数が $3$ 以下なら、補題「完全グラフに沿った貼り合わせ」から $\chi(G)\le\chi(G+uv)\le3$ となって矛盾する。よって、ある $i$ について $\chi(G_i^+)\ge4$ である。$G_i^+$ は $G$ より頂点が少なく、辺は $G[V_i]$ より高々 1 本多いだけで、$V_{3-i}\setminus V_i$ の頂点に接続する辺($G$ は連結なので 1 本以上ある)を含まないので、$\lvert G_i^+\rvert+e(G_i^+)< \lvert G\rvert+e(G)$ である。最小性から $G_i^+$ は $TK_4$ を部分グラフ $K$ として含む。$K$ が $G$ にない辺 $uv$ を使わなければ $K\subseteq G$ で矛盾する。使うなら、$K$ の辺 $uv$ を上で作った道(内部は $V_{3-i}\setminus V_i$ にあり $K$ と交わらない)に取り替えると、$G$ に含まれる $TK_4$ が得られ、やはり矛盾する。
3. 結論。 1、2 と $\lvert G\rvert\ge4$ から $G$ は 3-連結であり、Hadwiger予想 の補題「3-連結グラフの中の $K_4$」により $TK_4$ を含む。これは $G$ のとり方に反する。$\square$
BM76 Theorem 8.5(pp. 123–124)の証明は $G$ を 4-臨界グラフにとり、2 頂点による分離の構造についての定理を使う。上の証明は最小の反例を直接とり、その構造を使わずに済ませている。
グラフ $G$ に新しい頂点 $v$ を加え、$v$ を $G$ のすべての頂点と結んだグラフを $G\ast v$ と書く。$G\ast v$ のどの彩色でも $v$ の色は $G$ のどの頂点にも使われないので、$\chi(G\ast v)=\chi(G)+1$ である。
$t\ge1$ とする。$G\ast v$ が $TK_{t+1}$ を含めば、$G$ は $TK_t$ を含む。
$G\ast v$ に含まれる $TK_{t+1}$ を $L$ とし、その分岐点の 1 つ $x$ を次のように選ぶ。$v$ が $L$ の分岐点なら $x:=v$ とする。$v$ が $L$ の道 $P$ の分割点なら、$P$ の端点の一方を $x$ とする。$v$ が $L$ の頂点でなければ、$x$ は任意の分岐点とする。$L$ から $x$ と、$x$ を端点とする $t$ 本の道(端点以外の頂点を含む)を除くと、残りの $t$ 個の分岐点と、その間を結ぶ $\binom t2$ 本の道が残り、これは $TK_t$ である。どの場合も $v$ はこの $TK_t$ の頂点でない。分割点は 1 本の道にしか現れないからである。よって $TK_t$ は $G$ に含まれる。$\square$
2 は $\chi(G\ast v)=\chi(G)+1$ と lem-hj-apex から従う。1 は 2 の対偶である。$\square$
これは Hadwiger予想 の系「予想の単調性」の細分版である。とくに、ある $k_0$ で反例が 1 つ見つかれば、$k\ge k_0$ のすべてで $\mathrm{HJ}(k)$ が成り立たない。
添字を $\mathbb Z/5\mathbb Z$ の元とし、3 頂点ずつの互いに交わらない集合 $Q_0,\dots,Q_4$ をとる。$x\in Q_i$ と $y\in Q_j$($x\ne y$)を、$i-j\in\{0,1,-1\}$ のとき、かつそのときに限り辺で結んだ 15 頂点のグラフを $C_5[K_3]$ と書く。各 $Q_i$ は三角形で、$Q_i$ と $Q_{i\pm1}$ の間はすべて結ばれ、$Q_i$ と $Q_{i\pm2}$ の間には辺がない。
$C_5[K_3]$ は、閉路 $C_5$ の各頂点を三角形 $K_3$ に置き換えたもの(辞書式積)である。Moh05 §2(p. 2)は、これに 5 頂点を加えたグラフを、彩色数が $8$ で $TK_8$ を含まない曲面の三角形分割として与えている。以下の議論では、$\{i,i+2\}$ の形の添字の組を 離れた組 と呼ぶ。$x\in Q_i$ と $y\in Q_j$ が隣接しないのは、$\{i,j\}$ が離れた組のときに限る。
$\chi(C_5[K_3])=8$ である。
下界. 3 頂点の添字 $i,j,l$ を考える。$\mathbb Z/5\mathbb Z$ の 3 元のうちには、等しいか差が $\pm1$ の 2 元がある(閉路 $C_5$ の独立集合は 2 頂点以下)。よって $C_5[K_3]$ のどの 3 頂点にも辺があり、1 色に塗れる頂点は 2 個以下である。15 頂点を塗るには $\lceil15/2\rceil=8$ 色以上を要する。
上界. $Q_i=\{q_i^1,q_i^2,q_i^3\}$ とし、次の 8 個の集合をそれぞれ 1 色で塗る。
$$
\{q_0^1,q_2^1\},\ \{q_0^2,q_2^2\},\ \{q_0^3,q_3^1\},\ \{q_1^1,q_3^2\},\ \{q_1^2,q_3^3\},\ \{q_1^3,q_4^1\},\ \{q_2^3,q_4^2\},\ \{q_4^3\}.
$$
添字の組 $\{0,2\},\{0,3\},\{1,3\},\{1,4\},\{2,4\}$ はどれも離れた組なので、各集合の 2 頂点は隣接しない。15 頂点はちょうど 1 回ずつ現れるので、これは 8 色の彩色である。$\square$
$C_5[K_3]$ は $TK_8$ を部分グラフとして含まない。とくに $\mathrm{HJ}(8)$ は成り立たない。
$C_5[K_3]$ が $TK_8$ を含むとし、その分岐点の集合を $B$($\lvert B\rvert=8$)、残りの頂点の集合を $S$($\lvert S\rvert=7$)とする。$b_i:=\lvert B\cap Q_i\rvert$、$s_i:=3-b_i=\lvert S\cap Q_i\rvert$ とおくと、$0\le b_i\le3$、$\sum_ib_i=8$ である。
1. 分割点の数え上げ. $N_i:=b_ib_{i+2}$ は、$x\in B\cap Q_i$、$y\in B\cap Q_{i+2}$ である分岐点の組の個数である。この $x,y$ は隣接しないので、$x$ と $y$ を結ぶ道 $P_{xy}$ は分割点を 1 個以上もち、分割点は $S$ に属し、相異なる道は分割点を共有しない。$P_{xy}$ の分割点がちょうど 1 個 $z$ なら、$z$ は $x,y$ の両方に隣接するので、$z$ の添字は $i$ と $i+2$ のどちらとも差が $0,\pm1$ であり、$i+1$ に限る。よって、この $N_i$ 本の道のうち分割点が 1 個のものは $s_{i+1}$ 本以下で、残りは分割点を 2 個以上もつ。分割点の総数は $\lvert S\rvert=7$ 以下なので
$$
T:=\sum_{i}\bigl(2N_i-\min\{N_i,s_{i+1}\}\bigr)\le7
$$
である。以下、この不等式を (1) と書く。各項は $N_i$ 以上なので、$\sum_iN_i\le7$ でもある。
2. 離れた組の並べ替え. 離れた組をたどると添字は $0,2,4,1,3$ の順に巡回する。$c_0,\dots,c_4$ を $b_0,b_2,b_4,b_1,b_3$ とし、$c$ の添字も $\mathbb Z/5\mathbb Z$ で読むと、$\sum_iN_i=\sum_jc_jc_{j+1}$ である。また、$c_j,c_{j+1}$ が $b_a,b_{a+2}$ にあたるとき、$b_{a+1}$ は $c_{j+3}$ である($j=0$ なら $a=0$ で $b_1=c_3$。ほかの $j$ も同様)。$c_j>0$ となる $j$ の集合を $P$ とする。$c_j\le3$、$\sum_jc_j=8$ なので $\lvert P\rvert\ge3$ である。正の整数 $p,q$ について $(p-1)(q-1)\ge0$、すなわち $pq\ge p+q-1$ を使う。
3. 残る 2 つの場合. 1 の考察を $c$ の言葉で言い直すと、位置 $j,j+1$ の組の道 $c_jc_{j+1}$ 本のうち分割点が 1 個のものは、$3-c_{j+3}$ 本以下である。
$k\ge8$ のすべての整数について $\mathrm{HJ}(k)$ は成り立たない。$C_5[K_3]$ に、互いに隣接しすべての頂点と結ばれた $k-8$ 個の頂点を加えたグラフは、彩色数が $k$ で $TK_k$ を含まない。
thm-hj-catlin から始めて、cor-hj-lift の 2 を $k-8$ 回使う。新しい頂点を 1 つ加えるごとに彩色数はちょうど $1$ 増える。$\square$
$C_5[K_3]$ は $TK_7$ を含む。$B:=Q_0\cup Q_1\cup\{q_2^1\}$ を分岐点にとると、$Q_0\cup Q_1$ は 6 頂点の完全グラフで、$q_2^1$ は $Q_1$ の頂点と隣接し、$Q_0$ の 3 頂点 $q_0^m$ とは道 $q_2^1\,q_3^m\,q_4^m\,q_0^m$($m=1,2,3$)で結ばれる。これらの道は分割点を共有しない。したがって $C_5[K_3]$ は $\mathrm{HJ}(7)$ の反例ではない。Catlin は $k=7$ を含む $k\ge7$ のすべてで反例を与えている(Moh05 p. 1。原論文は Cat79)。
| 外した仮定・変えた主張 | 例 | 成り立たなくなる結論 |
|---|---|---|
| $k\le4$(thm-hj-dirac の $4$ を $8$ に) | $C_5[K_3]$ | $\chi\ge8$ なのに $TK_8$ を含まない |
| $\chi(G)\ge4$(thm-hj-dirac の仮定を $\chi\ge3$ に) | 閉路 $C_5$ | $TK_4$ を含む |
| 主張の向き($TK_k$ を含めば $\chi\ge k$) | 閉路 $C_4$ | $\chi\ge3$ |
1 行目は prop-hj-catlin-chi と thm-hj-catlin による。2 行目:$TK_4$ の分岐点は次数 $3$ をもつが、$C_5$ の頂点の次数は $2$ なので $TK_4$ を含まない。一方 $\chi(C_5)=3$ である。3 行目:ex-hj-small の 3 のとおりで、$C_4$ は $TK_3$ だが 2 色で塗れる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する