彩色数
概要
彩色数（chromatic number）とは、グラフ $G$ の頂点に、隣接する 2 頂点が異なる色になるように色を塗るとき（頂点彩色）に必要な色の個数の最小値 $\chi(G)$ のことである。$\chi(G)$ は頂点集合を独立集合に分割するときの個数の最小値でもある。頂点をもつ有限グラフでは、最大クリークの大きさ $\omega(G)$ と最大次数 $\Delta(G)$ について $\omega(G)\le\chi(G)\le\Delta(G)+1$ が成り立つが、下界は等号になるとは限らず、三角形を含まず彩色数がいくらでも大きいグラフもある。$\chi(G)\le2$ であることは奇数の長さの閉路を含まないことと同値であり、平面グラフでは $\chi(G)\le4$ である（四色定理）。辺を塗り分ける辺彩色数 $\chi'(G)$ とは別の量である。
前提知識: グラフ, 彩色, 完全グラフ, 二部グラフ, 次数(グラフ)
定義
本記事では、特に断らない限り、ループも平行辺ももたない有限の単純無向 グラフ $G=(V,E)$ を扱う（グラフ の記事の定義「グラフの定義」）。頂点の彩色は 彩色 の記事の定義に従う。すなわち、空でない集合 $S$ について、写像 $c\colon V\to S$ で、辺で結ばれた任意の 2 頂点 $x,y$ に対して $c(x)\ne c(y)$ となるものを $G$ の $S$-頂点彩色（頂点彩色）といい、$S=\{1,\dots,k\}$ のとき $k$-頂点彩色という。$k=0$ の場合も含めるため、$V=\emptyset$ のときは $\emptyset$ から $\{1,\dots,k\}$ への唯一の写像（空写像）を $k$-頂点彩色とみなす。
グラフ $G$ が $k$-彩色可能（$k$-colorable）であるとは、$G$ が $k$-頂点彩色をもつことをいう。$G$ が $k$-彩色可能となる最小の $k\in\mathbb{N}$ を $G$ の 彩色数（chromatic number）といい、$\chi(G)$ と書く。$\chi(G)=k$ であるとき、$G$ は $k$-彩色的（$k$-chromatic）であるという。
彩色数は 染色数 ともいう。
この最小値は存在する。各頂点に相異なる色を割り当てれば $|V|$-頂点彩色になる（彩色 の記事の命題「十分多い色による彩色」）ので、$\chi(G)\le|V|$ である。$k$-頂点彩色は $\{1,\dots,k\}\subset\{1,\dots,k+1\}$ によって $(k+1)$-頂点彩色でもあるから、$G$ が $k$-彩色可能であることと $\chi(G)\le k$ であることは同値である。$\chi(G)=0$ となるのは $V=\emptyset$ のときに限る。
辺彩色に必要な色の最小数は 辺彩色数 $\chi'(G)$ と呼ばれ、彩色数とは別の量である（彩色 の記事の注意「色の名前と色数」、本記事の補足）。単に「彩色数」というときは頂点彩色についての $\chi(G)$ を指す。
$k$-頂点彩色 $c$ の各色の頂点全体 $c^{-1}(i)$（色クラス）は独立集合であり、$V$ は $c^{-1}(1),\dots,c^{-1}(k)$ に分割される（空のものがあってもよい）。逆に $V$ を $k$ 個の独立集合 $I_1,\dots,I_k$ に分割すれば、$v\in I_i$ に色 $i$ を与えて $k$-頂点彩色が得られる。したがって $\chi(G)$ は、$V$ を独立集合に分割するときの個数の最小値である。$K$ がクリークであることは、$K$ が 補グラフ $\overline G$ の独立集合であることと同値なので、$\omega(G)=\alpha(\overline G)$ である。
直感
彩色数は「衝突するものどうしを別の組に入れるとき、最低いくつの組が要るか」を測る。頂点を授業、辺を「同じ時間に置けない」関係とすれば、彩色数は時間割に必要な時間帯の最小数である（彩色 の記事の直感）。互いに衝突する $r$ 個の対象（大きさ $r$ のクリーク）があれば組は $r$ 個以上要り、各対象の衝突相手が高々 $\Delta$ 個なら、1 つずつ順に空いた組へ入れていけば $\Delta+1$ 個で足りる（prop-chromatic-number-bounds）。しかし下界と上界の間は一般に大きく離れうる。三角形を含まなくても彩色数はいくらでも大きくなり（rem-chromatic-number-triangle-free）、彩色数を求めることは局所的な情報だけでは済まない大域的な問題である。
例と反例
- 頂点が $n\ge1$ 個で辺のない 空グラフ $E_n$ では、すべての頂点に同じ色を塗ればよいので $\chi(E_n)=1$ である。逆に、辺を 1 本でももつグラフは、その両端点に異なる色が要るので $\chi(G)\ge2$ である。
- 完全グラフ $K_n$ では $\chi(K_n)=n$ である（完全グラフ の記事の命題「彩色数とクリーク数」）。
- 閉路グラフ $C_n$（$n\ge3$）では、$n$ が偶数なら $\chi(C_n)=2$、$n$ が奇数なら $\chi(C_n)=3$ である。偶数の場合は 2 色を交互に塗る。奇数の場合は 2 色では塗れず（彩色 の記事の反例「奇閉路の2-頂点彩色」）、頂点 $1,\dots,n$ に $1,2,1,2,\dots,1,2,3$ と塗れば 3 色で足りる（最後の頂点 $n$ の隣は色 $2$ の頂点 $n-1$ と色 $1$ の頂点 $1$）。
- 辺を 1 本以上もつ 二部グラフ、とくに頂点が 2 個以上の 木、$m,n\ge1$ の 完全二部グラフ $K_{m,n}$ では $\chi=2$ である。部集合ごとに 1 色を塗れば 2-頂点彩色になり（彩色 の記事の例「二部グラフの2-頂点彩色」）、辺があるので 1 色では足りない。
外側の頂点 $v_0,\dots,v_4$、内側の頂点 $u_0,\dots,u_4$ をもち、辺が $v_iv_{i+1}$、$v_iu_i$、$u_iu_{i+2}$（添字は $5$ を法とする）である 10 頂点・15 辺のグラフを Petersenグラフ $P$ という。外側の頂点は長さ $5$ の奇閉路をなすので $\chi(P)\ge3$ である。
$$c(v_0,\dots,v_4)=(1,2,1,2,3),\qquad c(u_0,\dots,u_4)=(2,1,3,3,2)$$
と塗ると、外側の辺 $v_0v_1,\dots,v_4v_0$ の両端の色は $(1,2),(2,1),(1,2),(2,3),(3,1)$、辺 $v_iu_i$ では $(1,2),(2,1),(1,3),(2,3),(3,2)$、内側の辺 $u_0u_2,u_1u_3,u_2u_4,u_3u_0,u_4u_1$ では $(2,3),(1,3),(3,2),(3,2),(2,1)$ であり、いずれも異なる。よって $\chi(P)=3$ である。$P$ は 3 正則なので、これは $\chi\le\Delta$ の例でもある（thm-chromatic-number-brooks）。
閉路グラフ $C_5$ は三角形を含まないので $\omega(C_5)=2$ であるが、$\chi(C_5)=3$ である。満たす性質：最大のクリークの大きさが $2$ である。満たさない性質：2-彩色可能である。破る含意：「$\chi(G)=\omega(G)$」は一般には成り立たない。下界 $\omega(G)\le\chi(G)$（prop-chromatic-number-bounds）が等号になるとは限らない。$\chi(G)-\omega(G)$ はいくらでも大きくなりうる（rem-chromatic-number-triangle-free）。
$n\ge2$ とし、頂点 $a_1,\dots,a_n,b_1,\dots,b_n$ をもち、$i\ne j$ のときだけ $a_i$ と $b_j$ を結ぶ二部グラフ $H_n$（$K_{n,n}$ から完全マッチングを除いたもの）を考える。$\chi(H_n)=2$ である。頂点を $a_1,b_1,a_2,b_2,\dots,a_n,b_n$ の順に並べ、各頂点に「すでに色が付いた隣接頂点に使われていない最小の色」を与える（lem-chromatic-number-greedy の貪欲彩色）と、$a_i$ と $b_i$ はともに色 $i$ を受け取る。実際、$i$ についての帰納法で、$a_i$ より前に並ぶ隣接頂点は $b_1,\dots,b_{i-1}$ で色は $1,\dots,i-1$、$b_i$ より前に並ぶ隣接頂点は $a_1,\dots,a_{i-1}$ で色は $1,\dots,i-1$ だからである。したがってこの順序の貪欲彩色は $n$ 色を使い、$n\ge3$ のときこれは $\chi(H_n)=2$ より多い（$n=2$ では $2$ 色で、$\chi(H_2)$ に等しい）。一方 $a_1,\dots,a_n,b_1,\dots,b_n$ の順序なら 2 色で済む。破る含意：$n\ge3$ の $H_n$ により、「貪欲彩色はつねに $\chi(G)$ 色で済む」は成り立たない。ただし、順序をうまく選べば $\chi(G)$ 色で済む（lem-chromatic-number-greedy の 2）。
星グラフ $K_{1,n}$（$n\ge1$）では最大次数は $\Delta=n$ であるが、$\chi(K_{1,n})=2$ である。上界 $\chi(G)\le\Delta(G)+1$（prop-chromatic-number-bounds）は、$n$ が大きいとき実際の値から大きく離れる。この上界が等号になるのは、連結グラフでは完全グラフと奇閉路に限られる（thm-chromatic-number-brooks による）。
性質
- $c$ を $G$ の $\chi(G)$-頂点彩色とすると、その $V(H)$ への制限は $H$ の頂点彩色である。$H$ の辺は $G$ の辺なので、両端点の色は異なるからである。
- 1 により $\chi(G_i)\le\chi(G)$ なので $\max_i\chi(G_i)\le\chi(G)$ である。$k:=\max_i\chi(G_i)$ とし、各 $G_i$ の $k$-頂点彩色 $c_i$ をとる（$\chi(G_i)\le k$ なのでとれる）。連結成分の頂点集合は $V$ を分割するので、$v\in V(G_i)$ に $c_i(v)$ を与える写像 $c\colon V\to\{1,\dots,k\}$ が定まる。$G$ の各辺はある 1 つの成分の辺（グラフ の記事の命題「連結成分への分解」）なので両端点の色は異なり、$c$ は $G$ の $k$-頂点彩色である。$\square$
次の構成は彩色数の上界を与える基本的な方法である。
$G=(V,E)$ を $n$ 頂点のグラフとし、頂点を $v_1,\dots,v_n$ と並べる。$i=1,\dots,n$ の順に、$v_i$ に「$v_i$ に隣接する $v_1,\dots,v_{i-1}$ の頂点に使われていない最小の正の整数」を色 $g(v_i)$ として与える。
- $g$ は頂点彩色であり、各 $i$ について $g(v_i)\le1+|N_G(v_i)\cap\{v_1,\dots,v_{i-1}\}|$ である。
- 頂点の並べ方をうまく選べば、$g$ の使う色の個数は $\chi(G)$ に等しい。
- $v_i$ と $v_j$（$j< i$）が隣接すれば、$g(v_i)$ は $g(v_j)$ と異なるように選ばれるので、$g$ は頂点彩色である。$v_i$ より前の隣接頂点の個数を $d_i$ とすると、それらに使われている色は高々 $d_i$ 個なので、$\{1,\dots,d_i+1\}$ の中に使われていない色があり、$g(v_i)\le d_i+1$ である。
- $k:=\chi(G)$ とし、$k$-頂点彩色 $c$ をとる。頂点を $c$ の値の小さい順に並べる（同じ色の頂点の順は任意）。$g(v_i)\le c(v_i)$ を $i$ についての帰納法で示す。$v_i$ より前の隣接頂点 $v_j$ は、前にあるので $c(v_j)\le c(v_i)$、隣接するので $c(v_j)\ne c(v_i)$、すなわち $c(v_j)< c(v_i)$ であり、帰納法の仮定から $g(v_j)\le c(v_j)< c(v_i)$ である。よって前の隣接頂点に使われた色はすべて $c(v_i)$ より小さく、色 $c(v_i)$ は使われていないので、$g(v_i)\le c(v_i)\le k$ である。$g$ は $k$ 色以内の頂点彩色であり、彩色数の定義から $k$ 色より少なくはならない。$\square$
頂点を 1 個以上もつ $n$ 頂点のグラフ $G$ について、最大次数 を $\Delta(G)$ とすると
$$\max\Bigl\{\omega(G),\ \frac{n}{\alpha(G)}\Bigr\}\le\chi(G)\le\Delta(G)+1$$
が成り立つ。
大きさ $\omega(G)$ のクリーク $K$ の頂点は互いに隣接するので、どの頂点彩色でも相異なる色をもつ。よって $\chi(G)\ge|K|=\omega(G)$ である。$\chi(G)$-頂点彩色の色クラスは独立集合なので、それぞれ高々 $\alpha(G)$ 個の頂点しか含まず、$n\le\chi(G)\,\alpha(G)$ である（$n\ge1$ より $\alpha(G)\ge1$）。
上界：頂点を任意に並べて lem-chromatic-number-greedy の貪欲彩色 $g$ を作ると、各頂点の前の隣接頂点は高々 $\deg_G(v_i)\le\Delta(G)$ 個なので $g(v_i)\le\Delta(G)+1$ である。よって $G$ は $(\Delta(G)+1)$-彩色可能である。$\square$
2 色で足りるかどうかは、奇数の長さの閉路の有無で判定できる。
グラフ $G$ について $\chi(G)\le2$ であることと、$G$ が長さ奇数の 閉路 を含まないことは同値である。したがって、辺を 1 本以上もつグラフ $G$ について、$\chi(G)=2$ であることと、$G$ が奇閉路を含まないことは同値である。
$V=\emptyset$ なら両辺とも成り立つので、$V\ne\emptyset$ とする。二部グラフ の記事の命題「彩色による言い換え」（$r=2$ の場合）により、$\chi(G)\le2$ であることは $G$ が二部グラフであることと同値であり、同記事の定理「閉路の長さによる特徴付け」により、それは $G$ が奇閉路を含まないことと同値である。後半は、辺があれば $\chi(G)\ge2$ である（ex-chromatic-number-basic の 1）ことからしたがう。$\square$
3 色以上については、このような簡単な特徴づけは知られていない。
グラフ $G$ の頂点を 1 個以上もつすべての部分グラフ $H$ について 最小次数 $\delta(H)\le k$ であるとする。このとき $\chi(G)\le k+1$ である。
頂点の並べ方 $v_1,\dots,v_n$ を後ろから決める。$W_n:=V$ とし、誘導部分グラフ $G[W_i]$ で次数が $k$ 以下の頂点を 1 つ選んで $v_i$ とし、$W_{i-1}:=W_i\setminus\{v_i\}$ とする（仮定 $\delta(G[W_i])\le k$ によりとれる）。こうすると $W_i=\{v_1,\dots,v_i\}$ であり、$v_i$ に隣接する $v_1,\dots,v_{i-1}$ の頂点は $G[W_i]$ での $v_i$ の隣接頂点なので、高々 $k$ 個である。この並べ方で lem-chromatic-number-greedy の貪欲彩色を作れば、各頂点の色は $k+1$ 以下である。$\square$
平面グラフ $G$ について $\chi(G)\le6$ である。
平面グラフの部分グラフは、埋め込みを制限すれば平面グラフである。したがって prop-chromatic-number-degeneracy により、頂点を 1 個以上もつ平面グラフ $H$ が $\delta(H)\le5$ を満たすことを示せばよい。$H$ の頂点数 $m$ が $2$ 以下なら次数は $1$ 以下である。$m\ge3$ なら、平面グラフ の記事の系「単純平面グラフの辺数の上界」により $|E(H)|\le3m-6$ なので、握手補題 により次数の総和は $2|E(H)|\le6m-12<6m$ であり、次数が $5$ 以下の頂点がある。$\square$
実際には 4 色で足りる。
平面グラフ $G$ について $\chi(G)\le4$ である。
この定理は 四色定理 と呼ばれる。Appel と Haken（AH77）が計算機による膨大な場合の検証を用いて証明し、のちに Robertson・Sanders・Seymour・Thomas が簡略化した証明を与えた（Die17 §5.1 の注）。証明は本記事では扱わない。$\chi\le5$（五色定理）であれば、prf-chromatic-number-planar-six と同様に次数 $5$ 以下の頂点を取り除く議論に Kempe 鎖の入れ替えを加えて証明できる（Die17 §5.1）。$K_4$ は平面グラフで $\chi(K_4)=4$ なので、$4$ をそれより小さくすることはできない。
連結グラフでは、上界 $\Delta(G)+1$ が等号になるのは次の例外の場合に限られる。
連結グラフ $G$ が完全グラフでも奇閉路でもなければ、$\chi(G)\le\Delta(G)$ である。
この定理は Brooksの定理 と呼ばれ、Brooks（1941）による。証明は Die17 §5.2 に譲る。完全グラフ $K_n$ では $\chi=n=\Delta+1$、奇閉路では $\chi=3=\Delta+1$ なので、例外は除けない。連結でないグラフには、prop-chromatic-number-subgraph の 2 により各連結成分に適用すればよい。
補グラフの彩色数とは次の関係がある。
頂点を $n\ge1$ 個もつグラフ $G$ とその補グラフ $\overline G$ について
$$n\le\chi(G)\,\chi(\overline G),\qquad \chi(G)+\chi(\overline G)\le n+1$$
が成り立つ。
左の不等式：prop-chromatic-number-bounds により $n\le\chi(G)\,\alpha(G)$ である。$G$ の独立集合は $\overline G$ のクリークなので $\alpha(G)=\omega(\overline G)\le\chi(\overline G)$ であり、$n\le\chi(G)\,\chi(\overline G)$ を得る。
右の不等式：$n$ についての帰納法で示す。$n=1$ なら $\chi(G)=\chi(\overline G)=1$ である。$n\ge2$ とし、頂点 $v$ を 1 つとって $G':=G-v$（$v$ とそれに接続する辺を除いたグラフ）とおく。$\overline{G'}=\overline G-v$ である。$G'$ の $\chi(G')$-頂点彩色に、$v$ だけに新しい色を与えれば $G$ の頂点彩色になるので $\chi(G)\le\chi(G')+1$、同様に $\chi(\overline G)\le\chi(\overline{G'})+1$ である。
両方が等号でなければ、帰納法の仮定により $\chi(G)+\chi(\overline G)\le\chi(G')+\chi(\overline{G'})+1\le n+1$ である。両方が等号であるとする。$\deg_G(v)<\chi(G')$ ならば、$G'$ の $\chi(G')$-頂点彩色で $v$ の隣接頂点に使われていない色が残り、それを $v$ に与えて $\chi(G)\le\chi(G')$ となるので、$\deg_G(v)\ge\chi(G')$ である。同様に $\deg_{\overline G}(v)\ge\chi(\overline{G'})$ である。次数(グラフ) の記事の命題「補グラフにおける次数」により $\deg_G(v)+\deg_{\overline G}(v)=n-1$ なので、$\chi(G')+\chi(\overline{G'})\le n-1$ となり、$\chi(G)+\chi(\overline G)=\chi(G')+\chi(\overline{G'})+2\le n+1$ である。$\square$
この 2 つの不等式は Nordhaus と Gaddum による（Wes01 §5.1 の演習）。$K_n$ と $\overline{K_n}=E_n$ では $\chi(K_n)+\chi(E_n)=n+1$、$\chi(K_n)\chi(E_n)=n$ であり、どちらの不等式も等号が成り立つ。
下界 $\omega(G)\le\chi(G)$ は大きく外れうる。任意の $k\ge1$ について、三角形を含まない（$\omega(G)\le2$）で $\chi(G)=k$ となるグラフが存在する。グラフ $G$ から三角形を含まないまま彩色数を $1$ だけ増やす Mycielski の構成によってこれらを帰納的に作れ（Wes01 §5.2）、$k=4$ の場合は 11 頂点の Grötzsch グラフが得られる。さらに Erdős は、閉路の長さの最小値（内周）と彩色数がともにいくらでも大きいグラフの存在を確率的な方法で示した（Die17 §11.2）。これらのグラフでは、各頂点の近くを見ると木のように見えるにもかかわらず、少ない色では塗れない。
補足
- 辺彩色数：共通の端点をもつ辺どうしに異なる色を与える辺彩色の最小色数 $\chi'(G)$ は、線グラフ $L(G)$ の彩色数に等しい（彩色 の記事の命題「辺彩色と線グラフの頂点彩色」）。単純グラフでは $\Delta(G)\le\chi'(G)\le\Delta(G)+1$ が成り立つ（Vizing の定理、Die17 §5.3）。彩色数とは異なり、$\chi'(G)$ は 2 つの値のどちらかに限られる。詳しくは 辺彩色 を参照する。
- 彩色多項式：正の整数 $k$ について $G$ の $k$-頂点彩色の個数を $P_G(k)$ とすると、$P_G$ は $k$ の多項式である（彩色多項式）。$\chi(G)$ は $P_G(k)>0$ となる最小の $k$ である（$V\ne\emptyset$ のとき）。
- 無限グラフ：無限グラフでも頂点彩色と彩色数は同じ定義で考えられる（色の集合は無限でもよい）。有限部分グラフがすべて $k$-彩色可能なら無限グラフ全体も $k$-彩色可能である（de Bruijn–Erdős の定理、Die17 第 8 章）。
- 文献：彩色数の基本事項は Die17 第 5 章、BM08 第 14 章、Wes01 §5.1–5.2 にある。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
