Hajós予想

同義語:Hajós conjectureHajós's conjectureHajósの予想

概要

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$ は未解決である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 彩色数, 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 本の道も端点以外の頂点を共有しない。分岐点はどの道の内部にも現れない。

Hajós 予想

整数 $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)$ を導く。逆は成り立たない。

小さな例
  1. 長さ $5$ の閉路 $C_5$ は $\chi=3$ で、それ自身が $K_3$ の細分である。
  2. 車輪グラフ $W_5$(5 頂点の閉路と、そのすべての頂点に隣接する中心)は $\chi=4$ で、中心と外周の 3 頂点を分岐点にとれば $TK_4$ を含む。外周の残りの 2 頂点は外周の道の分割点になる。
  3. 長さ $4$ の閉路 $C_4$ は $K_3$ の細分だが、$\chi(C_4)=2$ である。$TK_k$ を含んでも彩色数が $k$ 以上とは限らない(BM76 p. 123)。

$k\le4$ の場合

$k\le3$ の場合

$\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$

Dirac の定理

$\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 頂点による分離の構造についての定理を使う。上の証明は最小の反例を直接とり、その構造を使わずに済ませている。

反例は $k$ を上げても反例のまま

グラフ $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$

予想の単調性と反例の持ち上げ
  1. $\mathrm{HJ}(k+1)$ が成り立てば $\mathrm{HJ}(k)$ も成り立つ。
  2. $\chi(G)\ge k$ で $TK_k$ を含まないグラフ $G$ があれば、$\chi(G\ast v)\ge k+1$ で $TK_{k+1}$ を含まないグラフ $G\ast v$ がある。

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)$ が成り立たない。

彩色数 8 の反例

閉路と三角形の辞書式積

添字を $\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\}$ が離れた組のときに限る。

$C_5[K_3]$ の彩色数

$\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]$ は $K_8$ の細分を含まない

$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$ を使う。

  • $\lvert P\rvert=5$ のとき:$\sum_jc_jc_{j+1}\ge\sum_j(c_j+c_{j+1}-1)=16-5=11$ となり、(1) に反する。
  • $\lvert P\rvert=4$ のとき:$c_{j+4}=0$ となる $j$ をとると、$\sum_ic_ic_{i+1}=c_jc_{j+1}+c_{j+1}c_{j+2}+c_{j+2}c_{j+3}\ge5+c_{j+1}+c_{j+2}$ である。これが $7$ 以下なので $c_{j+1}=c_{j+2}=1$、したがって $c_j=c_{j+3}=3$ である。
  • $\lvert P\rvert=3$ のとき:正の 3 つの値は $3,3,2$ である。3 つが $j,j+1,j+2$ と並ぶなら、和は $c_{j+1}(c_j+c_{j+2})\ge2\cdot5=10$ となり (1) に反する。そうでなければ、正の位置は $j,j+1$ と、その両方と隣り合わない $j+3$ であり、和は $c_jc_{j+1}$ である。これが $7$ 以下なので $\{c_j,c_{j+1}\}=\{3,2\}$、$c_{j+3}=3$ である。

3. 残る 2 つの場合. 1 の考察を $c$ の言葉で言い直すと、位置 $j,j+1$ の組の道 $c_jc_{j+1}$ 本のうち分割点が 1 個のものは、$3-c_{j+3}$ 本以下である。

  • $\lvert P\rvert=3$ の残りの場合:位置 $j,j+1$ の組の道は $6$ 本で、$c_{j+3}=3$ なので、どれも分割点を 2 個以上もつ。$T\ge12$ である。
  • $\lvert P\rvert=4$ の場合:位置 $j,j+1$ の組の道は $3$ 本で、$c_{j+3}=3$ なのでどれも分割点を 2 個以上もつ。位置 $j+2,j+3$ の組の道も $3$ 本で、$c_{j+5}=c_j=3$ なので同様である。$T\ge6+6=12$ である。
    どちらも (1) に反する。よって $TK_8$ は含まれない。prop-hj-catlin-chi と合わせて、$C_5[K_3]$ は $\mathrm{HJ}(8)$ の反例である。$\square$
$k\ge8$ の反例

$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=5,6$:未解決である(LW22 p. 2)。$\mathrm{HJ}(5)$ は、平面グラフが $TK_5$ を含まないこと(Kuratowskiの定理)を通じて四色定理を導く(Moh05 p. 1、LW22 p. 2)。
  • ほとんどすべてのグラフ:Erdős と Fajtlowicz は、ほとんどすべてのグラフで予想が成り立たないことを示した(Die25 第 7 章の注、p. 225。EF81)。$K_{s+1}$ の細分を含まず彩色数が $s^2/\log s$ の定数倍以上のグラフがあり、彩色数の上界としては $O(s^2)$ が知られている(LW22 p. 2)。
  • 成り立つ場合:内周(最短の閉路の長さ)が十分大きいグラフでは成り立つ(Die25 Corollary 7.3.9、p. 192)。線グラフでも成り立つことが C. Thomassen により示された(Die25 第 7 章の注、p. 225)。

反例と逆の表

外した仮定・変えた主張例成り立たなくなる結論
$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 色で塗れる。

関連項目

参考文献

[1]
J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Macmillan / American Elsevier, 1976, §8.3 p. 123(Hajós の予想、k≤3 の場合、C_4 の注意)、Theorem 8.5 pp. 123–124(Dirac:4 色を要するグラフは K_4 の細分を含む)
[2]
R. Diestel, Graph Theory (6th ed., Graduate Texts in Mathematics 173), Springer, 2025, Theorem 5.2.6 p. 131(Hajós の構成)、p. 192(Hajós 予想の述べ方と Corollary 7.3.9:内周の大きいグラフ)、第 7 章の注 p. 225(Catlin 1979、Erdős–Fajtlowicz、線グラフの場合)
[3]
Bojan Mohar, Triangulations and the Hajós conjecture, The Electronic Journal of Combinatorics, 2005, #N15。p. 1(序論:Dirac の k≤4、k=5 と四色定理、Catlin の k≥7 の反例、Erdős–Fajtlowicz)、§2 pp. 2–3(Theorem 2.1 と C_5[K_3] を含むグラフ)
[4]
Chun-Hung Liu; David R. Wood, Clustered variants of Hajós' conjecture, Journal of Combinatorial Theory, Series B, 2022, 刊行版 pp. 27–54。arXiv 版 v4(arXiv:1908.05597)の頁:要旨 p. 1(Catlin による否定、彩色数の Ω(s²/log s) の下界)、序論 p. 2(1940 年代の予想、s∈{4,5} で未解決、Catlin、Erdős–Fajtlowicz、Ω(s²/log s) の例と O(s²) の上界)
[5]
Paul A. Catlin, Hajós' graph-coloring conjecture: variations and counterexamples, Journal of Combinatorial Theory, Series B, 1979, 268–274
[6]
P. Erdős; S. Fajtlowicz, On the conjecture of Hajós, Combinatorica, 1981, 141–143

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する