全彩色予想(total coloring conjecture)とは、単純グラフの頂点と辺を、隣接する頂点、端点を共有する辺、頂点とそれに接続する辺がいつも異なる色になるように塗るとき、最大次数 $\Delta$ に対して $\Delta+2$ 色で足りるという Behzad と Vizing の予想である。1 つの頂点とその辺だけで $\Delta+1$ 色を要するので、必要な色の数は $\Delta+1$ か $\Delta+2$ のどちらかになるはずだと主張する。一般には未解決だが、二部グラフ、最大次数 2 以下のグラフ、完全グラフでは成り立ち、完全グラフでは頂点数の偶奇で $\Delta+1$ か $\Delta+2$ かが決まる。リスト辺彩色数に $2$ を足した上界もあり、最大次数 $5$ 以下の場合は証明されている。
全彩色予想(total coloring conjecture)は、単純グラフの頂点と辺を同時に塗り分けるのに必要な色の数が、最大次数 $\Delta$ に $2$ を足した数を超えない、という予想である。ここで塗り分けとは、隣接する 2 頂点、端点を共有する 2 辺、頂点とそれに接続する辺が、いつも異なる色になることをいう。1 つの頂点とそれに接続する辺は互いにすべて異なる色を要するので、$\Delta+1$ 色は必要である。予想は、あと 1 色だけで足りることを主張する。V. G. Vizing と M. Behzad が 1965 年ごろに提起し(Die25 p. 154)、一般には未解決である。
頂点だけの塗り分けでは彩色数が $\Delta+1$ 以下であり、辺だけの塗り分けでは Vizingの定理 により辺彩色数が $\Delta+1$ 以下である。全彩色予想は、この 2 つを重ねても色が 1 つしか増えないという主張にあたる。最大次数が $3$ の場合は M. Rosenfeld と N. Vijayaditya が、$5$ 以下の場合は A. V. Kostochka が証明した(BKW97 p. 54)。最大次数が十分大きいグラフでは $\Delta+10^{26}$ 色で足りることが M. Molloy と B. Reed により示されている(GNS23 p. 1)。この記事では、上下の基本的な評価、二部グラフでの予想、完全グラフと閉路の全彩色数の決定、リスト辺彩色による上界を証明する。
この記事のグラフは有限な単純グラフとし、$V(G)$ を頂点の集合、$E(G)$ を辺の集合、$\Delta(G)$ を最大次数とする。頂点と辺をまとめて $G$ の 要素 と呼ぶ。2 つの要素が 衝突する とは、隣接する 2 頂点、端点を共有する相異なる 2 辺、頂点とそれに接続する辺のいずれかであることをいう。
正の整数 $k$ について、写像 $c\colon V(G)\cup E(G)\to\{1,\dots,k\}$ で、衝突する 2 つの要素にいつも異なる値を与えるものを $G$ の $k$-全彩色(total $k$-coloring)という。$G$ が $k$-全彩色をもつ最小の $k$ を $G$ の 全彩色数(total chromatic number)といい、$\chi''(G)$ と書く。
要素を頂点とし、衝突する 2 つの要素を辺で結んだグラフを $G$ の 全グラフ $T(G)$ という。全彩色は $T(G)$ の頂点彩色と同じもので、$\chi''(G)=\chi(T(G))$ である。$T(G)$ は、$G$ 自身と線グラフ $L(G)$ を含み、さらに頂点と接続する辺を結んだグラフである。全彩色の定義は Die25 の演習 34(p. 150)による。
すべての単純グラフ $G$ について $\chi''(G)\le\Delta(G)+2$ が成り立つ、という予想を 全彩色予想(Behzad–Vizing 予想)という。
下の prop-tc-bounds から $\chi''(G)\ge\Delta(G)+1$ なので、予想が正しければ、単純グラフは $\chi''=\Delta+1$ のもの(第 1 型)と $\chi''=\Delta+2$ のもの(第 2 型)に分かれる(GNS23 p. 1)。辺彩色 の第 1 類・第 2 類と同じ形の分け方である。
単純グラフ $G$ について
$$
\Delta(G)+1\le\chi''(G)\le2\Delta(G)+1
$$
が成り立つ。
下界. 次数 $\Delta:=\Delta(G)$ の頂点 $v$ と、$v$ に接続する $\Delta$ 本の辺を考える。$v$ はそれぞれの辺と衝突し、それらの辺はどの 2 本も $v$ を共有して衝突するので、この $\Delta+1$ 個の要素はすべて異なる色を要する。
上界. Vizingの定理 により、辺を色 $1,\dots,\Delta+1$ で塗り分けられる。次に頂点を 1 つずつ塗る。頂点 $v$ の色として使えないのは、$v$ に接続する辺の色(高々 $\Delta$ 個)と、すでに塗った隣接頂点の色(高々 $\Delta$ 個)だけである。よって色 $1,\dots,2\Delta+1$ のうち使える色が残り、すべての頂点を塗れる。$\Delta+1\le2\Delta+1$ なので、辺の色もこの範囲にある。$\square$
上界は粗いが、頂点と辺の塗り分けを「辺から先に、頂点をあとから」と分けて考える型を示している。次の命題は、辺の塗り分けをリストつきに強めると、頂点を先に塗っても $2$ 色の増加で済むことを述べる。
各辺 $e$ に色の集合 $S_e$(リスト)が与えられたとき、隣接する辺に異なる色を与え、各辺 $e$ の色を $S_e$ から選ぶ塗り分けを、リストからの辺彩色という。大きさ $k$ のリストをどう与えてもリストからの辺彩色が存在する最小の $k$ を $G$ の リスト辺彩色数(list-chromatic index)といい、$\mathrm{ch}'(G)$ と書く(Die25 p. 134。頂点についての定義は Thomassenの定理(リスト彩色) の定義「リスト彩色と選択数」)。すべてのリストを $\{1,\dots,k\}$ にとれば通常の辺彩色なので、$\mathrm{ch}'(G)\ge\chi'(G)\ge\Delta(G)$ である。
単純グラフ $G$ について $\chi''(G)\le\mathrm{ch}'(G)+2$ である。
$k:=\mathrm{ch}'(G)$ とおく。彩色数 の命題「彩色数の基本評価」により $\chi(G)\le\Delta(G)+1\le k+1$ なので、頂点を色 $1,\dots,k+2$ で塗り分けた頂点彩色 $c$ がとれる。各辺 $e=uv$ について、$\{1,\dots,k+2\}\setminus\{c(u),c(v)\}$ は $k$ 個以上の色を含むので、その中から $k$ 個を選んでリスト $S_e$ とする。$\mathrm{ch}'(G)=k$ なので、リスト $S_e$ からの辺彩色がある。隣接する辺は異なる色をもち、辺 $uv$ の色は $c(u),c(v)$ と異なる。よって $c$ とこの辺彩色を合わせたものは $(k+2)$-全彩色である。$\square$
1 は prop-tc-list と Vizingの定理 の $\chi'\le\Delta+1$ による。2 は、任意の $\varepsilon>0$ について最大次数が十分大きいグラフは $\mathrm{ch}'(G)\le(1+\varepsilon)\Delta(G)$ をみたすという J. Kahn の定理(Die25 p. 154。この記事では証明しない)と prop-tc-list による。$\square$
これは Die25 の演習 34(p. 150)が問うている評価である。リスト彩色予想は Die25 p. 137 に述べられ、二部グラフでは F. Galvin が証明した(同 Theorem 5.4.4、p. 138)。
二部グラフ $G$ について $\chi''(G)\le\Delta(G)+2$ である。
$G$ に辺がなければ、すべての頂点を 1 色で塗れる。辺があるとし、$\Delta:=\Delta(G)$ とする。Königの辺彩色定理 により、辺を色 $1,\dots,\Delta$ で塗り分けられる。頂点の 2 つの部を $X,Y$ とし、$X$ の頂点に色 $\Delta+1$、$Y$ の頂点に色 $\Delta+2$ を塗る。隣接する 2 頂点は異なる部にあるので色が異なり、頂点の色は辺のどの色とも異なる。よってこれは $(\Delta+2)$-全彩色である。$\square$
二部グラフでも $\chi''=\Delta+2$ となるものがある。下の thm-tc-cycle により、長さ $4$ の閉路 $C_4$ は $\chi''=4=\Delta+2$ である。
$n\ge1$ とする。$n$ が奇数なら $\chi''(K_n)=n$、$n$ が偶数なら $\chi''(K_n)=n+1$ である。とくに $K_n$ は、$n$ が奇数なら第 1 型、偶数なら第 2 型である。
$\Delta(K_n)=n-1$ なので、prop-tc-bounds から $\chi''(K_n)\ge n$ である。
$n$ が奇数のとき. 頂点を $\mathbb Z/n\mathbb Z$ の元 $0,1,\dots,n-1$ とし、頂点 $i$ に色 $2i\bmod n$、辺 $\{i,j\}$ に色 $i+j\bmod n$ を塗る。頂点 $i$ に接続する辺の色 $i+j$($j\ne i$)は $j$ ごとに異なり、頂点 $i$ の色 $2i$ は $j\ne i$ のどの $i+j$ とも異なる。$n$ は奇数なので $2$ は $\mathbb Z/n\mathbb Z$ で逆元をもち、相異なる頂点の色 $2i,2j$ は異なる。よってこれは $n$-全彩色であり、$\chi''(K_n)=n$ である。辺の色の付け方は 辺彩色 の定理「完全グラフの辺彩色数」の証明と同じで、各頂点で辺に使われずに残る色をその頂点に塗っている。
$n$ が偶数のとき. 上界:$K_n$ は $K_{n+1}$ から 1 頂点を除いたもので、$n+1$ は奇数なので、$K_{n+1}$ の $(n+1)$-全彩色を制限すれば $K_n$ の $(n+1)$-全彩色が得られる。下界:$K_n$ が $n$-全彩色 $c$ をもつとして矛盾を導く。各頂点 $v$ について、$v$ と $v$ に接続する $n-1$ 本の辺は互いに衝突するので、$n$ 色がちょうど 1 回ずつ現れる。頂点はどの 2 つも隣接するので頂点の色は相異なり、各色はちょうど 1 つの頂点に使われる。色 $\alpha$ を塗られた頂点を $u$ とする。$u$ 以外の頂点 $v$ では、$v$ 自身の色は $\alpha$ でないので、$v$ に接続する辺のちょうど 1 本が色 $\alpha$ をもつ。この辺の他端は $u$ でない($u$ に接続する辺の色は $u$ の色 $\alpha$ と異なる)。よって色 $\alpha$ の辺は、$u$ 以外の $n-1$ 個の頂点をちょうど 1 回ずつ覆う辺の集合で、$n-1$ は偶数でなければならない。これは $n$ が偶数であることに反する。$\square$
偶数の場合の議論は、全彩色で $\Delta+1$ 色しか使わないと、各色の辺が頂点 1 つを除いて完全マッチングにならなければならないことを示している。頂点の数の偶奇がこれを妨げる。
$n\ge3$ とし、$C_n$ を長さ $n$ の閉路とする。$n$ が $3$ の倍数なら $\chi''(C_n)=3$、そうでなければ $\chi''(C_n)=4$ である。
$C_n$ の頂点を $v_1,\dots,v_n$、辺を $e_i:=v_iv_{i+1}$($v_{n+1}:=v_1$)とし、要素を $v_1,e_1,v_2,e_2,\dots,v_n,e_n$ の順に円周に並べた長さ $2n$ の巡回列を考える。この列で隣り合う 2 つ(頂点とそれに接続する辺)と、1 つおいて隣り合う 2 つ(隣接する 2 頂点、または端点を共有する 2 辺)は衝突し、それ以外の 2 つは衝突しない。よって全彩色とは、この巡回列の連続する 3 項がいつも相異なるような色の付け方のことである。
3 色の場合. 3 色で塗れたとすると、連続する 3 項が $1,2,3$ の並べ替えなので、各項の色は 3 つ前の項の色と等しい($a_{t+3}$ は $a_{t+1},a_{t+2}$ と異なり、$a_t$ も同じ 2 色と異なる)。巡回列なので $a_{t+2n}=a_t$ でもある。$3\nmid 2n$ なら $3u+2nw=1$ となる整数 $u,w$ があり、$a_{t+1}=a_t$ となって、隣り合う 2 項が異なることに反する。よって $3\mid2n$ で、$3$ と $2$ は互いに素なので $3\mid n$ である。逆に $3\mid n$ なら、$1,2,3$ を繰り返して塗ればよい。$\chi''\ge3$ は prop-tc-bounds による。
4 色で足りること. $3\nmid n$ とする。長さ $3$ の区切り $1,2,3$ と長さ $4$ の区切り $1,2,3,4$ を何個かずつ並べて長さ $2n$ の巡回列を作る。区切りの境目をまたぐ連続 3 項は $2,3,1$、$3,1,2$、$3,4,1$、$4,1,2$ のどれかなので相異なり、区切りの中の連続 3 項も相異なる。$2n=3a+4b$ となる $a,b\ge0$ は、$2n\equiv1\pmod3$ なら $b=1$、$2n\equiv2\pmod3$ なら $b=2$ でとれる($3\nmid n$ と $n\ge3$ から、このとき $2n\ge8$ である)。$\square$
$\Delta(G)\le2$ の単純グラフ $G$ は $\chi''(G)\le\Delta(G)+2$ をみたす。
$\Delta(G)=0$ なら $\chi''(G)=1$ である。$\Delta(G)=1$ なら $G$ は互いに交わらない辺と孤立点からなり、各辺とその両端を 3 色で塗れる。$\Delta(G)=2$ なら、$G$ の連結成分は道と閉路である。$m\ge3$ 頂点の道は閉路 $C_m$ の部分グラフで、全彩色は部分グラフに制限しても全彩色なので、thm-tc-cycle から 4 色で塗れる。頂点が 2 個以下の道も 3 色で塗れる。連結成分の間には衝突がないので、同じ 4 色で成分ごとに塗ればよい。$\square$
閉路では、第 2 型になるかどうかが長さを $3$ で割った余りで決まる。辺彩色 では閉路が第 2 類になるのは長さが奇数のときであり、2 つの分け方は一致しない。たとえば $C_6$ は辺彩色で第 1 類、全彩色で第 1 型だが、$C_4$ は辺彩色で第 1 類、全彩色で第 2 型である。
| 外した仮定・変えた主張 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 単純グラフ(def-tc-conjecture) | 3 頂点の各対を $3$ 本ずつの辺で結んだ多重グラフ | $\chi''\le\Delta+2=8$ |
| 上界 $\Delta+2$ を $\Delta+1$ に下げる | $K_4$ | $\chi''(K_4)\le\Delta+1=4$ |
| $n$ が $3$ の倍数(thm-tc-cycle の $\chi''=3$) | $C_4$ | $\chi''(C_4)=3$ |
1 行目:平行な辺を許し、衝突の定義は同じとする。各頂点の次数は $6$ である。辺は $9$ 本で、3 頂点のうち 2 頂点を結ぶ辺どうしはどの 2 本も端点を共有するので、$9$ 本すべてが異なる色を要する。よって $\chi''\ge9>8$ である(辺だけの場合の同じ例は 多重グラフ の例「太い三角形」)。2 行目:thm-tc-complete により $\chi''(K_4)=5$ である。3 行目:thm-tc-cycle により $\chi''(C_4)=4$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する