# 彩色：Brooks の定理・Vizing の定理・彩色多項式

> Brooks・Mycielski・König・Vizing の定理、彩色多項式と Whitney の展開、平面的グラフの 5-リスト彩色可能性（Thomassen）、弦グラフと弱パーフェクトグラフ定理（Lovász）を、証明を省かずに示す。
> https://rikai.mugen-giken.com/mathematics/graph-theory/graph-colouring

## 0. この記事の要点

地図の隣り合う国を違う色で塗り分けるとき、色は何色あれば足りるでしょうか。点を線で結んだ図（グラフ）で同じことを考えるのが、この記事の主題です。必要な色の数を、見やすい量で上と下から押さえる定理、色の塗り方が何通りあるかを数える多項式、塗れる色がマスごとに違うときの扱い、そして「色の数がいつでもぴったり決まる」グラフの族を順に見ます。読み終えると、色の数を見積もる基本の道具と、塗り替えの技法が使えるようになります。

- グラフの彩色数 $\chi$ は、クリーク数 $\omega$ 以上、最大次数 $\Delta$ に 1 を足した数以下です。上界が $\Delta+1$ に届くのは、連結グラフでは完全グラフと奇閉路だけです（**Brooks の定理**）。下界は当てになりません。三角形を含まないのに彩色数がいくらでも大きいグラフがあります（**Mycielski の定理**）。
- 辺彩色数 $\chi'$ は $\Delta$ か $\Delta+1$ のどちらかです（**Vizing の定理**）。二部グラフではつねに $\Delta$ です（**König の辺彩色定理**）。証明の道具は、2 色の辺が作る道の上で色を入れ替える Kempe 鎖（2 色だけに注目してできる、色が交互に並ぶ道）の操作です。
- $k$ 色での彩色の個数 $P(G,k)$ は $k$ の多項式で、辺の除去と縮約についての漸化式を満たし、係数の符号が交代します。包除原理から、辺集合についての和の公式（**Whitney の展開**）が得られます。
- 頂点ごとに使える色のリストが違ってもよいリスト彩色では、[平面的グラフ](/mathematics/graph-theory/planar-graphs#def-plane-graph)はリストの大きさ 5 で必ず塗れます（**Thomassen の定理**）。これは五色定理の別証明にもなります。二部グラフでも、必要なリストの大きさはいくらでも大きくなります。
- どの誘導部分グラフ（頂点の一部を選び、それらの間の辺をすべて残したグラフ）でも $\chi=\omega$ となるグラフをパーフェクトグラフ（perfect graph）と呼びます。弦グラフ（長さ 4 以上のどの閉路にも、閉路の辺ではなく、閉路上の 2 頂点を結ぶ辺がある）はパーフェクトです。グラフがパーフェクトなら[補グラフ](/mathematics/graph-theory/paths-cycles-trees#def-subgraph)もパーフェクトです（**弱パーフェクトグラフ定理**）。証明は、[独立集合](/mathematics/graph-theory/matchings#def-covers)とクリークの接続行列の階数を比べる線形代数です。

<Aside type="tip" title="この記事で使う事前知識">

- **独立集合**: どの 2 頂点も隣接しない頂点の集合。→ [独立集合](/mathematics/graph-theory/matchings#def-covers)
- **マッチング**: どの 2 辺も端点を共有しない辺の集合。→ [マッチング](/mathematics/graph-theory/matchings#def-matching)
- **連結成分**: グラフの中で、辺をたどって行き来できる頂点のまとまりのうち、最大のもの。→ [連結成分](/mathematics/graph-theory/paths-cycles-trees#def-connected)
- **切断点**: それを取り除くとグラフが連結でなくなる頂点。→ [切断点](/mathematics/graph-theory/paths-cycles-trees#def-bridge)
- **辺連結度**: 連結でなくするために取り除く辺の最小の本数。→ [辺連結度](/mathematics/graph-theory/connectivity-and-flows#def-connectivity)
- **縮約**: 辺の両端の 2 頂点を 1 つにまとめる操作。→ [縮約](/mathematics/graph-theory/kuratowski-theorem#def-minor)

</Aside>

## 1. 動機

試験の時間割を作るとします。同じ学生が受ける 2 科目は、同じ時間帯に置けません。科目を頂点とし、共通の受験者がいる 2 科目を辺で結ぶと、時間帯の割り当ては「隣接する頂点に違う色を塗る」ことに当たり、必要な時間帯の最小数がグラフの**彩色数**です。地図の塗り分け、無線の周波数の割り当て、計算機のレジスタの割り当ても同じ形の問題です。

彩色数を求めるのは一般には難しい問題です（3 色で塗れるかの判定は NP 完全、つまり効率のよい解き方が知られていない難しい問題の代表格です）。そこで、次数やクリークのような見やすい量で彩色数を上下から評価すること、評価が鋭い場合を特定すること、特別なグラフの族では正確に求めることが、理論の中心になります。この章の定理は、どれもこの 3 つのどれかに当たります。

もう 1 つの主題は、**色の塗り替え**です。途中まで塗った彩色が行き詰まったとき、2 色だけに注目して、その 2 色の頂点（または辺）がつながっている部分で色を入れ替えると、彩色を壊さずに局所的な状況を変えられます。この Kempe 鎖の操作は、[平面グラフの章](/mathematics/graph-theory/planar-graphs)の五色定理（<Ref to="mathematics/graph-theory/planar-graphs#thm-five-colour" />）で一度使いました。この章では、辺彩色の 2 つの定理で主役になります。

## 2. 準備：彩色数と、すぐ分かる評価

グラフは有限・単純・無向とし、記法は[道・閉路・木の章](/mathematics/graph-theory/paths-cycles-trees)に従います。$n=|V(G)|$、$m=|E(G)|$ です。独立集合と独立数 $\alpha(G)$ は <Ref to="mathematics/graph-theory/matchings#def-covers" /> のとおりです。

<Definition id="def-chromatic-number" title="彩色・彩色数・クリーク数">
集合 $S$ への写像 $c:V(G)\to S$ で、隣接するどの 2 頂点 $u,v$ についても $c(u)\ne c(v)$ となるものを $G$ の（頂点）**彩色**といい、$S$ の元を**色**という。$|S|=k$ のとき **$k$-彩色**という（<Ref to="mathematics/graph-theory/planar-graphs#def-proper-colouring" /> と同じ）。色 $s$ の頂点の全体 $c^{-1}(s)$ を**色クラス**という。$G$ が $k$-彩色をもつような最小の $k$ を**彩色数** $\chi(G)$ という。

どの 2 頂点も隣接する頂点集合を**クリーク**といい、クリークの頂点数の最大値を**クリーク数** $\omega(G)$ という。
</Definition>

色クラスは[独立集合](/mathematics/graph-theory/matchings#def-covers)です。したがって $k$-彩色とは、頂点集合を $k$ 個の独立集合に分割することです。[補グラフ](/mathematics/graph-theory/paths-cycles-trees#def-subgraph) $\overline G$ では、クリークと独立集合が入れ替わるので、$\omega(\overline G)=\alpha(G)$、$\alpha(\overline G)=\omega(G)$ です。

<Definition id="def-degenerate" title="縮退数・彩色数（coloring number）">
$G$ の空でないどの部分グラフ $H$ も次数 $k$ 以下の頂点をもつとき、$G$ は **$k$-縮退**であるという。$\max_{H\subseteq G}\delta(H)$（$H$ は空でない部分グラフを動く）を $G$ の**縮退数**、それに 1 を足した数を $\operatorname{col}(G)$ と書く。
</Definition>

<Proposition id="prop-greedy-bound" title="彩色数の基本的な評価">
$n\ge1$ 頂点のグラフ $G$ について
$$
\max\Bigl(\omega(G),\ \frac{n}{\alpha(G)}\Bigr)\le\chi(G)\le1+\max_{H\subseteq G}\delta(H)\le1+\Delta(G)
$$
が成り立つ。
</Proposition>

<Proof of="prop-greedy-bound">
**下界.** クリークの頂点は互いに隣接するので、すべて違う色でなければならず、$\chi\ge\omega$ です。$\chi$-彩色の色クラスは独立集合で、大きさは $\alpha$ 以下です。$\chi$ 個の色クラスが $n$ 頂点を覆うので $n\le\chi\alpha$ です。

**上界.** $d=\max_{H\subseteq G}\delta(H)$ とおきます。頂点を次のように並べます。$G_n=G$ とし、$G_i$ の最小次数の頂点を $v_i$、$G_{i-1}=G_i-v_i$ と、$i=n,n-1,\dots,1$ の順に定めます。$G_i=G[\{v_1,\dots,v_i\}]$ で、$v_i$ の $G_i$ での次数は $\delta(G_i)\le d$ です。つまり、$v_i$ の隣接点のうち $v_1,\dots,v_{i-1}$ に入るものは $d$ 個以下です。

$v_1,v_2,\dots,v_n$ の順に、色 $1,\dots,d+1$ のうち、すでに塗った隣接点に使われていない最小の番号の色を塗ります（**貪欲彩色**）。$v_i$ を塗るとき、塗り終えた隣接点は $d$ 個以下なので、$d+1$ 色のうち使える色が残っています。こうして $(d+1)$-彩色が得られます。最後の不等式は、$H\subseteq G$ なら $\delta(H)\le\Delta(H)\le\Delta(G)$ だからです。
</Proof>

<Example id="ex-greedy-order" title="貪欲彩色は頂点の順序で悪くなる">
完全二部グラフ $K_{n,n}$（2 つの側を $a_1,\dots,a_n$ と $b_1,\dots,b_n$ とする）から、完全マッチング $a_1b_1,\dots,a_nb_n$ を除いたグラフ $G$ を考えます。$G$ は二部グラフなので $\chi(G)=2$ です（$n\ge2$）。

頂点を $a_1,b_1,a_2,b_2,\dots,a_n,b_n$ の順に並べて貪欲彩色をします。$a_1$ と $b_1$ は隣接しないので、どちらも色 1 です。帰納的に $a_j,b_j$（$j<i$）が色 $j$ だとすると、$a_i$ は $b_1,\dots,b_{i-1}$ と隣接するので色 $1,\dots,i-1$ が使えず、色 $i$ になります。$b_i$ も同様に色 $i$ です。結局 $n$ 色を使います。<Ref to="prop-greedy-bound" /> の証明のように順序を選ぶことが効いています（このグラフの縮退数は $n-1$ なので、あの順序でも保証されるのは $n$ 色までですが、$a_1,\dots,a_n,b_1,\dots,b_n$ の順なら 2 色で済みます）。
</Example>

<Example id="ex-petersen-chi" title="Petersen グラフの彩色数は 3">
Petersen グラフの頂点を $0,\dots,9$ とし、辺を外側の五角形 $01,12,23,34,40$、内側の星形 $57,79,96,68,85$、スポーク $05,16,27,38,49$ とします。長さ 5 の閉路を含むので二部グラフではなく（<Ref to="mathematics/graph-theory/paths-cycles-trees#thm-bipartite-odd-cycle" />）、$\chi\ge3$ です。次の表は 3-彩色です。

| 頂点 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 色 | 1 | 2 | 1 | 2 | 3 | 2 | 1 | 3 | 3 | 2 |

15 本の辺の両端の色は、外側が $(1,2),(2,1),(1,2),(2,3),(3,1)$、内側が $(2,3),(3,2),(2,1),(1,3),(3,2)$、スポークが $(1,2),(2,1),(1,3),(2,3),(3,2)$ で、どれも異なります。よって $\chi=3$ です。$\omega=2$、$\Delta=3$ なので、<Ref to="prop-greedy-bound" /> の上下の評価はどちらも等号になりません。
</Example>

## 3. 色臨界グラフ

彩色数が $k$ であることの「原因」を取り出すには、余分な部分を削れるだけ削ります。

<Definition id="def-critical" title="色臨界グラフ">
$\chi(G)=k$ で、$G$ のどの真部分グラフ $H$ についても $\chi(H)<k$ であるとき、$G$ は **$k$-色臨界**であるという。
</Definition>

彩色数が $k$ のグラフは、$k$-色臨界な部分グラフを含みます（彩色数が $k$ の部分グラフのうち、頂点数と辺数の和が最小のものを取ればよい）。$k$-色臨界グラフは連結です（非連結なら、彩色数は[連結成分](/mathematics/graph-theory/paths-cycles-trees#def-connected)の彩色数の最大値で、その成分が彩色数 $k$ の真部分グラフになります）。$1$-色臨界グラフは $K_1$、$2$-色臨界グラフは $K_2$、$3$-色臨界グラフは奇閉路です。

次の命題は、色臨界グラフには次数の小さい頂点がなく、少数の辺を除いてもつながりが切れないことを述べます。最小次数の主張は、次数が小さい頂点を取り除いて塗り、あとで戻す、という素朴な議論です。辺連結度の主張は背理法で示します。少ない辺で切れたと仮定して両側を別々に塗り、一方の色の名前を付け替えて貼り合わせると、色が 1 つ少ない彩色ができてしまう、という筋です。

<Proposition id="prop-critical" title="色臨界グラフの次数と辺連結度">
$k\ge2$ とし、$G$ を $k$-色臨界グラフとする。このとき $\delta(G)\ge k-1$ で、$G$ は $(k-1)$-辺連結である。
</Proposition>

<Proof of="prop-critical">
**最小次数.** $d(v)\le k-2$ である頂点 $v$ があるとします。$G-v$ は真部分グラフなので $(k-1)$-彩色をもちます。$v$ の隣接点に現れる色は $k-2$ 色以下なので、$k-1$ 色のうち残っている色を $v$ に塗ると $G$ の $(k-1)$-彩色になり、$\chi(G)=k$ に反します。

**辺連結度.** $(k-1)$-辺連結でないとすると、$k-2$ 本以下の辺の集合 $F$ で $G-F$ が非連結になるものがあります（<Ref to="mathematics/graph-theory/connectivity-and-flows#def-connectivity" />）。$G-F$ の連結成分の 1 つの頂点集合を $X$、残りを $Y$ とすると、$X,Y$ は空でなく、$X$ と $Y$ を結ぶ $G$ の辺はすべて $F$ に属します。

$G[X]$ と $G[Y]$ は真部分グラフなので、色集合 $\{1,\dots,k-1\}$ での彩色をもちます。その色クラスを $X_1,\dots,X_{k-1}$、$Y_1,\dots,Y_{k-1}$（空のものがあってもよい）とします。$X_i$ と $Y_j$ を結ぶ $G$ の辺がないとき $i$ と $j$ は**両立する**ということにし、$A=\{1,\dots,k-1\}$ の写しを 2 つ用意して、両立する $i$ と $j$ を結んだ二部グラフ $B$ を作ります。両立しない組 $(i,j)$ ごとに $F$ の辺が少なくとも 1 本あり、異なる組には異なる辺が対応するので、両立しない組は $k-2$ 個以下です。

$B$ が Hall の条件（<Ref to="mathematics/graph-theory/matchings#thm-hall-marriage" />）を満たすことを示します。$I\subseteq A$、$|I|=s\ge1$ とし、$|N_B(I)|\le s-1$ と仮定します。$N_B(I)$ に入らない $j$ は $k-1-(s-1)=k-s$ 個以上あり、それぞれが $I$ のどの元とも両立しないので、両立しない組は $s(k-s)$ 個以上です。$1\le s\le k-1$ では
$$
s(k-s)-(k-1)=(s-1)(k-1-s)\ge0
$$
なので、$s(k-s)\ge k-1>k-2$ となって矛盾です。よって $|N_B(I)|\ge|I|$ で、$B$ は完全マッチングをもちます。すなわち、$\{1,\dots,k-1\}$ の置換 $\pi$ で、各 $i$ について $i$ と $\pi(i)$ が両立するものがあります。

$Y_{\pi(i)}$ の頂点の色を $i$ に塗り替えます。$G[Y]$ の中では色の名前を付け替えただけなので彩色のままです。$X$ と $Y$ を結ぶ辺の両端が同じ色 $i$ なら、$X_i$ と $Y_{\pi(i)}$ を結ぶ辺があることになり、両立することに反します。こうして $G$ の $(k-1)$-彩色が得られ、$\chi(G)=k$ に反します。
</Proof>

辺の数を数えると、$k$-色臨界グラフでは $2m\ge(k-1)n$ です。「彩色数が大きいグラフは、どこかに辺の密な部分をもつ」ことを、この命題は定量的に述べています。ただし、密であることはクリークがあることを意味しません（<Ref to="thm-mycielski" />）。

## 4. Brooks の定理と Mycielski の構成

### 4.1. Brooks の定理

$\chi\le\Delta+1$ で等号が成り立つ例は、完全グラフ $K_n$（$\chi=n$、$\Delta=n-1$）と奇閉路（$\chi=3$、$\Delta=2$）です。連結グラフでは、これ以外にありません。

貪欲彩色で $\Delta$ 色に収めるには、各頂点を塗る時点で「まだ塗っていない隣接点が 1 つ残っている」か「塗った隣接点に同じ色が 2 回現れる」かのどちらかであればよいことに注目します。

<Lemma id="lem-greedy-order" title="1 頂点に向かう順序">
$G$ を連結グラフ、$v$ をその頂点とする。$G$ の頂点の並べ方 $v_1,\dots,v_n=v$ で、どの $v_i$（$i<n$）も自分より後ろに隣接点をもつものがある。
</Lemma>

<Proof of="lem-greedy-order">
頂点を、$v$ からの距離 $d(v_i,v)$ が大きい順に並べます（等しいものの順は任意）。$v$ は距離 0 で最後です。$v_i\ne v$ から $v$ への最短の道の上で、$v_i$ の次の頂点は $v$ からの距離がちょうど 1 小さいので、$v_i$ より後ろに並んでいて、$v_i$ と隣接します。
</Proof>

2-連結でない場合と、3-連結でない場合の処理のために、連結グラフの「端の部分」を取り出す補題を用意します。ブロック木（<Ref to="mathematics/graph-theory/connectivity-and-flows#prop-block-tree" />）の言葉では、葉に当たるブロックから切断点を除いた部分です。ここではブロックを使わずに直接示します。

この補題のねらいは、次の Brooks の定理の場合 3 (ii) で、隣接しない 2 つの隣接点 $a,b$ を選ぶことです。直感的には、切断点で切り分けていったときの一番端にある 2 つの「袋」$D_1,D_2$ を取り出す補題です。袋の中の頂点はどれも切断点でなく、2 つの袋の頂点をどのように 1 つずつ除いても、残りはつながったままです。

<Lemma id="lem-end-pieces" title="切断点をもつ連結グラフの 2 つの端">
$H$ を、切断点をもつ連結グラフとする。このとき、頂点 $c_1,c_2$ と、空でない互いに交わらない頂点集合 $D_1,D_2$ で、次を満たすものがある。

1. $D_j$ は $H-c_j$ の連結成分（の頂点集合）である（$j=1,2$）。
2. $D_1\cup D_2$ の頂点は、どれも $H$ の切断点ではない。
3. $D_1$ と $D_2$ を結ぶ辺はない。
4. どの $a\in D_1$、$b\in D_2$ についても、$H-\{a,b\}$ は連結である。
</Lemma>

<Proof of="lem-end-pieces">
**$D_1$ の選び方.** 切断点 $c$ と $H-c$ の連結成分 $D$ の組 $(c,D)$ のうち、$|D|$ が最小のものを $(c_1,D_1)$ とします。$H-c_1$ は非連結なので、$D_1$ と異なる連結成分 $D^\circ$ があります。

**$D_2$ の選び方.** 組 $(c,D)$ のうち $D\subseteq D^\circ$ であるもの（$(c_1,D^\circ)$ がその 1 つ）の中で、$|D|$ が最小のものを $(c_2,D_2)$ とします。$D_2\subseteq D^\circ$ なので、$D_1$ と $D_2$ は交わらず、$H-c_1$ の異なる成分に含まれるので、結ぶ辺はありません。これで 1 と 3 が成り立ちます。また $c_1\notin D_2$ です。$H$ は連結なので $c_2$ は $D_2$ に隣接点をもち、$D^\circ$ の頂点の隣接点は $D^\circ\cup\{c_1\}$ に属するので、$c_2\notin D_1$ です。

**2 を示す.** $d\in D_j$ が $H$ の切断点だとします。$H-d$ の連結成分のうち $c_j$ を含まないもの $D''$ を取ります。$H$ は連結なので $D''$ は $d$ の隣接点 $u$ を含みます。$u$ は $D_j\cup\{c_j\}$ に属し、$c_j$ ではないので $u\in D_j$ です。$D''$ は $H-c_j$ の連結な部分グラフで $D_j$ と交わるので $D''\subseteq D_j\setminus\{d\}$ です。$(d,D'')$ は、$j=1$ なら $|D_1|$ の最小性に、$j=2$ なら（$D''\subseteq D^\circ$ なので）$|D_2|$ の最小性に反します。

**4 を示す.** $R=H-D_1-D_2$ とおきます。まず $R$ は連結です。$H-D_2$ は、$c_2$ と、$H-c_2$ の $D_2$ 以外の連結成分からなり、$H$ が連結なのでどの成分も $c_2$ に隣接点をもつので、連結です。$D_1$ は $H-D_2$ に含まれ（$D_1\cap D_2=\varnothing$）、$c_1\in V(H-D_2)$ で、$D_1$ は $(H-D_2)-c_1$ の連結成分でもあります。同じ議論で $(H-D_2)-D_1=R$ は連結です。$R$ は $c_1,c_2$ を含みます。

$a\in D_1$、$b\in D_2$ とします。$u\in D_1\setminus\{a\}$ を取ります。2 から $a$ は切断点でないので $H-a$ は連結で、$u$ から $c_1$ への道があります。$D_1$ は $H-c_1$ の連結成分なので、この道は $c_1$ に着くまで $D_1$ の中を進み、$b$ を通りません。よって $u$ は $H-\{a,b\}$ の中で $c_1\in R$ とつながります。$D_2\setminus\{b\}$ の頂点も同様に $c_2\in R$ とつながります。$R$ は連結なので、$H-\{a,b\}$ は連結です。
</Proof>

<Theorem id="thm-brooks" title="Brooks の定理">
$G$ を連結グラフとする。$G$ が完全グラフでも奇閉路でもなければ
$$
\chi(G)\le\Delta(G)
$$
である。
</Theorem>

<Proof of="thm-brooks">
$k=\Delta(G)$ とおきます。

**$k\le2$ の場合.** $k\le1$ の連結グラフは $K_1$ か $K_2$ で、完全グラフです。$k=2$ なら、$G$ は道か閉路です（<Ref to="mathematics/graph-theory/matchings#lem-degree-two-components" />）。完全グラフでも奇閉路でもないので、$G$ は 3 頂点以上の道か偶閉路で、頂点に交互に 2 色を塗れば彩色になり、$\chi=2=\Delta$ です。

以下 $k\ge3$ とします。

**場合 1: 次数が $k$ 未満の頂点 $v$ がある.** <Ref to="lem-greedy-order" /> の順序 $v_1,\dots,v_n=v$ で貪欲彩色をします。$i<n$ のとき、$v_i$ は後ろに隣接点をもつので、塗り終えた隣接点は $d(v_i)-1\le k-1$ 個以下です。$v_n=v$ の隣接点は $k-1$ 個以下です。どの頂点でも $k$ 色のうち使える色が残るので、$k$-彩色が得られます。

**場合 2: $G$ は $k$-正則で、切断点 $v$ をもつ.** $G-v$ の連結成分の頂点集合を $C_1,\dots,C_r$（$r\ge2$）とし、$G_i=G[C_i\cup\{v\}]$ とおきます。$G$ は連結なので $v$ はどの $C_i$ にも隣接点をもち、$G_i$ は連結で、$v$ の $G_i$ での次数は $k$ 未満です。場合 1 の議論（最大次数が $k$ 以下で、次数 $k$ 未満の頂点をもつ連結グラフに使えます）から、各 $G_i$ は $k$-彩色をもちます。色の名前を付け替えて $v$ の色をそろえ、合わせると $G$ の $k$-彩色です（異なる $C_i$ を結ぶ辺はありません）。

**場合 3: $G$ は $k$-正則で、切断点をもたない.** 次を満たす 3 頂点 $v,a,b$ があることを示します。

> $a,b$ は $v$ の隣接点で、$a$ と $b$ は隣接せず、$G-\{a,b\}$ は連結である。

これがあれば定理が従います。$G-\{a,b\}$ に <Ref to="lem-greedy-order" /> を使って $v$ を最後にする順序を取り、その前に $a,b$ を置いた順序 $a,b,v_1,\dots,v_{n-2}=v$ で貪欲彩色をします。$a$ と $b$ は隣接しないので、どちらも色 1 です。$v_i$（$i<n-2$）は後ろに隣接点をもつので、塗り終えた隣接点は $k-1$ 個以下です。$v$ の $k$ 個の隣接点のうち $a,b$ は同じ色なので、隣接点に現れる色は $k-1$ 色以下です。どの頂点でも $k$ 色のうち使える色が残ります。

3 頂点の存在を示します。$n\ge k+1\ge4$ です。

*(i) $G$ が 3-連結のとき.* $G$ は完全グラフでないので、隣接しない 2 頂点があります。それらを結ぶ最短の道の最初の 3 頂点を $a,v,b$ とすると、$a$ と $b$ は $v$ の隣接点で、道が最短なので隣接しません。3-連結なので $G-\{a,b\}$ は連結です。

*(ii) $G$ が 3-連結でないとき.* $n\ge4$ なので、2 個以下の頂点からなる分離集合があります。$G$ は連結で切断点をもたないので、それは 2 頂点 $\{v,w\}$ です。$H=G-v$ は連結で、$w$ は $H$ の切断点です。<Ref to="lem-end-pieces" /> の $c_1,c_2,D_1,D_2$ を取ります。$v$ が $D_1$ に隣接点をもたなければ、$G$ の中で $D_1$ の頂点の隣接点は $D_1\cup\{c_1\}$ に属し、$c_1$ が $D_1$ を $v$ から切り離す $G$ の切断点になってしまいます。よって $v$ は $D_1$ に隣接点 $a$ を、同様に $D_2$ に隣接点 $b$ をもちます。補題の 3 から $a$ と $b$ は隣接しません。補題の 4 から $H-\{a,b\}$ は連結です。$d(v)=k\ge3$ なので $v$ は $a,b$ 以外にも隣接点をもち、$G-\{a,b\}$ は連結です。
</Proof>

<Remark id="rem-brooks-kempe" title="Kempe 鎖による証明">
Brooks 自身の議論（1941 年）は、次数 $\Delta$ の頂点のまわりで Kempe 鎖を入れ替えるものでした。ここで書いたのは Lovász が 1975 年に見つけた議論で、塗る順序をうまく選ぶだけで済みます。「隣接点に同じ色を 2 回使わせる」ために、先に $a,b$ を同じ色で塗っておくのが要点です。
</Remark>

### 4.2. 三角形を含まず彩色数が大きいグラフ

$\chi\ge\omega$ の逆向きの評価、つまり「彩色数が大きければ大きなクリークがある」は成り立ちません。

<Definition id="def-mycielski" title="Mycielski の構成">
グラフ $G$（頂点 $v_1,\dots,v_n$）に対し、新しい頂点 $v_1',\dots,v_n'$ と $w$ を足し、辺を

- $G$ の辺、
- $v_iv_j\in E(G)$ のときの $v_i'v_j$ と $v_iv_j'$、
- $v_i'w$（$i=1,\dots,n$）

としたグラフを $M(G)$ と書く。頂点は $2n+1$ 個、辺は $3m+n$ 本である。
</Definition>

<Theorem id="thm-mycielski" title="Mycielski の定理">
$G$ が三角形を含まなければ、$M(G)$ も三角形を含まない。また $\chi(M(G))=\chi(G)+1$ である。したがって、どの $k\ge1$ に対しても、三角形を含まない彩色数 $k$ のグラフが存在する。
</Theorem>

<Proof of="thm-mycielski">
**三角形.** $M(G)$ の三角形 $T$ があるとします。$v_1',\dots,v_n'$ は互いに隣接せず、$w$ の隣接点は $v_i'$ だけなので、$T$ は $w$ を含まず、$v_i'$ を高々 1 つ含みます。$T$ が $G$ の頂点だけからなれば $G$ の三角形です。$T=\{v_i',v_j,v_l\}$ なら、$v_i'v_j,v_i'v_l\in E(M(G))$ から $v_iv_j,v_iv_l\in E(G)$ で、$v_jv_l\in E(G)$ と合わせて $\{v_i,v_j,v_l\}$ が $G$ の三角形です（$v_i$ は $v_j,v_l$ と隣接するので、それらと異なります）。どちらにしても $G$ が三角形を含みます。

**$\chi(M(G))\le\chi(G)+1$.** $G$ の $\chi(G)$-彩色 $c$ を取り、$v_i'$ に $c(v_i)$ を、$w$ に新しい色を塗ります。$v_i'$ の隣接点は $w$ と、$v_i$ の $G$ での隣接点 $v_j$ で、$c(v_j)\ne c(v_i)$ なので彩色です。

**$\chi(M(G))\ge\chi(G)+1$.** $k=\chi(G)$ とし、$M(G)$ の $k$-彩色 $c$ があると仮定します。色の名前を付け替えて $c(w)=k$ とします。$v_i'$ は $w$ と隣接するので $c(v_i')\ne k$ です。$G$ の頂点の色を
$$
c^*(v_i)=\begin{cases}c(v_i)&(c(v_i)\ne k)\\ c(v_i')&(c(v_i)=k)\end{cases}
$$
と定めると、$c^*$ は色 $1,\dots,k-1$ だけを使います。$c^*$ が $G$ の彩色であることを確かめます。辺 $v_iv_j$ について、$c(v_i),c(v_j)$ の両方が $k$ であることはありません。どちらも $k$ でなければ $c^*=c$ で、色は異なります。$c(v_i)=k$、$c(v_j)\ne k$ なら、$c^*(v_i)=c(v_i')$、$c^*(v_j)=c(v_j)$ で、$v_i'$ と $v_j$ は $M(G)$ で隣接するので異なります。よって $G$ が $(k-1)$-彩色をもつことになり、矛盾です。

**最後の主張.** $M_1=K_1$、$M_2=K_2$、$M_{k+1}=M(M_k)$（$k\ge2$）と定めると、帰納法で $M_k$ は三角形を含まず、$\chi(M_k)=k$ です。
</Proof>

<Example id="ex-grotzsch" title="Grötzsch グラフ">
$M(K_2)$ は、$v_1v_2$、$v_1'v_2$、$v_1v_2'$、$v_1'w$、$v_2'w$ の 5 辺からなる長さ 5 の閉路 $v_1v_2v_1'wv_2'$ で、$\chi=3$ です。$M(C_5)$ は頂点 $2\cdot5+1=11$ 個、辺 $3\cdot5+5=20$ 本のグラフで、**Grötzsch グラフ**と呼ばれます。<Ref to="thm-mycielski" /> から、三角形を含まず、彩色数は 4 です。一方、三角形を含まない**平面的**グラフは 3-彩色可能であることが知られていて（Grötzsch の定理）、Grötzsch グラフは平面的ではありません。実際、三角形を含まないので[内周](/mathematics/graph-theory/paths-cycles-trees#def-connected)は 4 以上で、平面的なら辺は $2(n-2)=18$ 本以下でなければならず（<Ref to="mathematics/graph-theory/planar-graphs#cor-planar-edge-bound" />）、$20>18$ です。
</Example>

Mycielski のグラフは三角形を含みませんが、長さ 4 や 5 の閉路はたくさん含みます。短い閉路をすべて禁止しても彩色数を大きくできること（Erdős の定理）は、[次の章](/mathematics/graph-theory/extremal-and-ramsey)で確率的方法を使って示します。

## 5. 辺彩色

### 5.1. 定義と Kempe 鎖

<Definition id="def-edge-colouring" title="辺彩色・辺彩色数">
写像 $c:E(G)\to S$ で、端点を共有するどの 2 辺にも異なる色を与えるものを**辺彩色**という。$|S|=k$ の辺彩色をもつような最小の $k$ を**辺彩色数** $\chi'(G)$ という。辺彩色 $c$ と頂点 $v$ について、$v$ に接続するどの辺の色でもない色は、$v$ で**欠けている**という。
</Definition>

同じ色の辺の集合はマッチングです。辺彩色とは、辺集合をマッチングに分割することです。1 つの頂点に接続する辺はすべて違う色なので、$\chi'(G)\ge\Delta(G)$ です。

<Lemma id="lem-kempe-swap" title="Kempe 鎖の入れ替え（辺彩色）">
$c$ を $G$ の辺彩色、$\alpha,\beta$ を相異なる色とする。色が $\alpha$ または $\beta$ の辺とその端点からなる部分グラフを $H_{\alpha\beta}$ とする。

1. $H_{\alpha\beta}$ の連結成分は、道か偶閉路で、辺の色は $\alpha$ と $\beta$ が交互に並ぶ。
2. $H_{\alpha\beta}$ の 1 つの連結成分 $P$ の上で $\alpha$ と $\beta$ を入れ替えたものも辺彩色である。このとき、$P$ の頂点では「$\alpha$ が欠けている」と「$\beta$ が欠けている」が入れ替わり、他の色の現れ方と、$P$ の外の頂点での色の現れ方は変わらない。
</Lemma>

<Proof of="lem-kempe-swap">
1: 各頂点に接続する色 $\alpha$ の辺、色 $\beta$ の辺はそれぞれ高々 1 本なので、$H_{\alpha\beta}$ の最大次数は 2 以下で、連結成分は道か閉路です（<Ref to="mathematics/graph-theory/matchings#lem-degree-two-components" />）。隣り合う 2 辺は端点を共有するので色が異なり、$\alpha$ と $\beta$ が交互に並びます。閉路では一周して元に戻るので、長さは偶数です。

2: 端点を共有する 2 辺 $e,e'$ を取ります。どちらも $P$ の辺なら、入れ替え前に色が異なり、入れ替え後も異なります。$e$ が $P$ の辺で $e'$ がそうでなければ、$e'$ は共有する端点（$P$ の頂点）に接続するので、色が $\alpha$ か $\beta$ なら同じ成分 $P$ に入ってしまいます。よって $e'$ の色は $\alpha,\beta$ 以外で、$e$ の新しい色と異なります。どちらも $P$ の辺でなければ何も変わりません。色の現れ方についての主張は、$P$ の頂点に接続する色 $\alpha,\beta$ の辺がすべて $P$ の辺であることから従います。
</Proof>

$H_{\alpha\beta}$ の連結成分を、色 $\alpha,\beta$ の **Kempe 鎖**（交互道）と呼びます。頂点 $v$ で $\alpha$ が欠けていて $\beta$ が現れるなら、$v$ は $H_{\alpha\beta}$ で次数 1 なので、$v$ を含む Kempe 鎖は $v$ を端点とする道です。$\alpha$ も $\beta$ も欠けていれば、$v$ は $H_{\alpha\beta}$ の頂点ではなく、入れ替えるものはありません。

### 5.2. 二部グラフ

<Theorem id="thm-konig-edge-colouring" title="König の辺彩色定理">
二部グラフ $G$ について $\chi'(G)=\Delta(G)$ である。
</Theorem>

<Proof of="thm-konig-edge-colouring">
$\chi'\ge\Delta$ は上で見ました。$\Delta=\Delta(G)$ 色の辺彩色があることを、辺の数 $m$ についての帰納法で示します。$m=0$ なら何も塗るものがありません。$m\ge1$ とし、辺 $xy$ を取ります。$G-xy$ は二部グラフで最大次数は $\Delta$ 以下なので、帰納法の仮定から、色 $1,\dots,\Delta$ による辺彩色 $c$ をもちます。

$G-xy$ での $x,y$ の次数は $\Delta-1$ 以下なので、$x$ で欠けている色 $\alpha$ と、$y$ で欠けている色 $\beta$ があります。$\alpha$ が $y$ でも欠けていれば、$xy$ に $\alpha$ を塗って終わりです。

$\alpha$ が $y$ で現れるとします。このとき $\alpha\ne\beta$ で、$y$ は $H_{\alpha\beta}$ で次数 1 です。$y$ を含む Kempe 鎖 $P$ は $y$ を端点とする道で、$y$ での辺の色は $\alpha$ です。$x\in P$ と仮定します。$x$ では $\alpha$ が欠けているので、$x$ は $P$ のもう一方の端点で、$x$ での辺の色は $\beta$ です。$P$ は色 $\alpha$ の辺で始まり色 $\beta$ の辺で終わる交互道なので、長さは偶数です。すると $P$ に辺 $xy$ を足した閉路は長さが奇数で、$G$ が二部グラフであることに反します（<Ref to="mathematics/graph-theory/paths-cycles-trees#thm-bipartite-odd-cycle" />）。よって $x\notin P$ です。

$P$ の上で $\alpha$ と $\beta$ を入れ替えます（<Ref to="lem-kempe-swap" />）。$y$ では $\alpha$ が欠けるようになり、$x$ は $P$ の外なので $\alpha$ が欠けたままです。$xy$ に $\alpha$ を塗れば、$G$ の $\Delta$ 色の辺彩色です。
</Proof>

<Example id="ex-timetable" title="時間割の作成">
教員の集合 $A$ と学級の集合 $B$ があり、教員 $a$ が学級 $b$ を週に 1 コマ教えるとき $a$ と $b$ を辺で結びます。1 つの時間帯に、各教員は 1 学級しか教えられず、各学級は 1 人からしか習えないので、同じ時間帯の授業はマッチングです。時間割は辺彩色で、必要な時間帯の最小数は $\chi'$ です。<Ref to="thm-konig-edge-colouring" /> から、それは「最も忙しい教員のコマ数」と「最も授業の多い学級のコマ数」の大きいほう $\Delta$ に等しく、それより多くは要りません。

$K_{n,n}$ の $n$ 色の辺彩色は、$a_i b_j$ に色 $i+j \bmod n$ を塗れば得られます。色を行列の $(i,j)$ 成分に書くと、各行・各列に $n$ 色が 1 回ずつ現れる Latin 方陣です。
</Example>

### 5.3. Vizing の定理

二部グラフでなければ $\chi'=\Delta$ とは限りません。三角形は $\Delta=2$、$\chi'=3$ です。しかし、ずれは高々 1 です。証明では、色の付いていない辺 $xy_0$ から出発して、$x$ のまわりに下の図のような「扇」を作り、色を 1 つずつずらします。

証明の方針を先に述べます。辺を 1 本だけ塗らずに残し、ほかを $\Delta+1$ 色で塗っておきます。どの頂点でも色が 1 つは余っているので、残した辺の端点 $x$ のまわりで辺の色を 1 本ずつずらしていけば、残した辺に色を回せることがあります。ずらせないときには、2 色の Kempe 鎖の上で色を入れ替えて、ずらせる状況を作ります。場合 1 がずらすだけの場合、場合 2 が入れ替えてからずらす場合です。

<Figure caption="Vizing の定理の証明で使う扇。辺 xy₀ にはまだ色がない。辺 xy₁, xy₂, xy₃ の色 α₀, α₁, α₂ は、それぞれ 1 つ前の頂点 y₀, y₁, y₂ で欠けている色である。y₃ で欠けている色 α₃ が x でも欠けていれば、各辺 xyᵢ を色 αᵢ に塗り替えて（ずらして）全部の辺に色が付く。">
<svg viewBox="0 0 340 200" width="100%" role="img" aria-label="頂点 x から 4 つの隣接点 y0 から y3 へ辺が出ている扇の図">
  <path d="M 170 170 L 50 70" stroke="currentColor" stroke-width="1.6" stroke-dasharray="5 4" fill="none" />
  <path d="M 170 170 L 125 40" stroke="currentColor" stroke-width="1.8" fill="none" />
  <path d="M 170 170 L 215 40" stroke="currentColor" stroke-width="1.8" fill="none" />
  <path d="M 170 170 L 290 70" stroke="currentColor" stroke-width="1.8" fill="none" />
  <circle cx="170" cy="170" r="4.5" fill="var(--sl-color-accent)" />
  <circle cx="50" cy="70" r="4" fill="currentColor" /><circle cx="125" cy="40" r="4" fill="currentColor" />
  <circle cx="215" cy="40" r="4" fill="currentColor" /><circle cx="290" cy="70" r="4" fill="currentColor" />
  <text x="166" y="190" font-size="13" fill="currentColor">x</text>
  <text x="30" y="62" font-size="13" fill="currentColor">y₀</text><text x="112" y="30" font-size="13" fill="currentColor">y₁</text>
  <text x="210" y="30" font-size="13" fill="currentColor">y₂</text><text x="296" y="64" font-size="13" fill="currentColor">y₃</text>
  <text x="82" y="130" font-size="11" fill="currentColor">色なし</text>
  <text x="152" y="100" font-size="12" fill="var(--sl-color-accent)">α₀</text>
  <text x="196" y="100" font-size="12" fill="var(--sl-color-accent)">α₁</text>
  <text x="240" y="126" font-size="12" fill="var(--sl-color-accent)">α₂</text>
</svg>
</Figure>

<Theorem id="thm-vizing" title="Vizing の定理">
どのグラフ $G$ についても
$$
\Delta(G)\le\chi'(G)\le\Delta(G)+1
$$
である。
</Theorem>

<Proof of="thm-vizing">
$\Delta=\Delta(G)$ とし、$\Delta+1$ 色の辺彩色があることを、辺の数についての帰納法で示します。辺がなければ明らかです。辺 $xy_0$ を取り、$G-xy_0$ の $\Delta+1$ 色の辺彩色 $c$ を帰納法の仮定から得ます。色は $\Delta+1$ 個あり、どの頂点の次数も $\Delta$ 以下なので、**どの頂点でも少なくとも 1 色が欠けています。** $x$ で欠けている色を 1 つ選んで $\beta$ とします。

**扇を作る.** $x$ の相異なる隣接点の列 $y_0,y_1,\dots,y_k$ と色の列 $\alpha_0,\dots,\alpha_k$ で、

- $\alpha_i$ は $y_i$ で欠けている色（$0\le i\le k$）、
- $c(xy_{i+1})=\alpha_i$（$0\le i<k$）

を満たすものを**扇**と呼びます。$y_0$ だけの列（$\alpha_0$ は $y_0$ で欠けている色）は扇です。$\alpha_0,\dots,\alpha_{k-1}$ は $x$ に接続する相異なる辺の色なので相異なります。扇を次のように伸ばせるだけ伸ばします。$y_k$ で欠けている色 $\alpha_k$ を選び、色 $\alpha_k$ の辺 $xy$ があって $y\notin\{y_1,\dots,y_k\}$ なら、$y_{k+1}=y$ として伸ばします。$x$ の隣接点は有限個なので、この操作は止まります。止まったとき、次のどちらかです。

**場合 1: $\alpha_k$ が $x$ で欠けている.** 辺 $xy_i$ の色を $\alpha_i$ に塗り替えます（$i=0,\dots,k$。$xy_0$ には初めて色が付きます）。これを**扇をずらす**と呼びます。$y_i$ では、$\alpha_i$ は欠けていた色なので、他の辺と衝突しません。$x$ では、辺 $xy_1,\dots,xy_k$ の色 $\alpha_0,\dots,\alpha_{k-1}$ が辺 $xy_0,\dots,xy_{k-1}$ に移り、$xy_k$ が $x$ で欠けていた色 $\alpha_k$ になるので、$x$ に接続する辺の色は相異なったままです。$G$ の辺彩色が得られました。

**場合 2: $\alpha_k$ が $x$ で現れる.** 色 $\alpha_k$ の辺 $xy$ があり、扇が伸ばせないので $y=y_j$（$1\le j\le k$）、すなわち $\alpha_k=c(xy_j)=\alpha_{j-1}$ です。$\alpha=\alpha_k=\alpha_{j-1}$ とおきます。$\alpha$ は $x$ で現れ、$\beta$ は $x$ で欠けているので $\alpha\ne\beta$ です。

色 $\alpha,\beta$ の Kempe 鎖を調べます。$H_{\alpha\beta}$ で、$x$ の次数は 1（接続するのは辺 $xy_j$ だけ）、$y_{j-1}$ と $y_k$ の次数は 1 以下（どちらも $\alpha$ が欠けている）です。$x$ を含む Kempe 鎖 $P$ は $x$ を端点とする道で、$x,y_{j-1},y_k$ の 3 頂点すべてが $P$ の端点になることはできません。また、扇の辺と色について次が成り立ちます。

- (a) 扇の辺 $xy_i$（$i\ge1$）の色 $\alpha_{i-1}$ は $\beta$ ではなく、$\alpha$ であるのは $i=j$ のときだけである。辺 $xy_j$ は $P$ の辺である。
- (b) $i<k$ のとき $\alpha_i\ne\beta$ で、$\alpha_i=\alpha$ となるのは $i=j-1$ のときだけである（$\alpha_i=c(xy_{i+1})$ なので (a) から従う）。

*場合 2a: $y_{j-1}\notin P$.* $y_{j-1}$ を含む Kempe 鎖 $P'$（$y_{j-1}$ が $H_{\alpha\beta}$ の頂点でなければ何もしない）の上で $\alpha$ と $\beta$ を入れ替えます。$y_{j-1}$ では $\beta$ が欠けるようになります。$x$ は $P'$ の外なので、$\beta$ は $x$ で欠けたままで、$x$ に接続する辺の色は変わりません。$i<j-1$ について、$\alpha_i$ は (b) から $\alpha$ でも $\beta$ でもないので、$y_i$ で欠けたままです。したがって、$y_0,\dots,y_{j-1}$ と色 $\alpha_0,\dots,\alpha_{j-2},\beta$ は、最後の色 $\beta$ が $x$ で欠けている扇です。場合 1 のとおりにずらせば、$G$ の辺彩色になります。

*場合 2b: $y_{j-1}\in P$.* このとき $P$ の端点は $x$ と $y_{j-1}$ なので、$y_k\notin P$ です。$y_k$ を含む Kempe 鎖 $P''$ の上で $\alpha$ と $\beta$ を入れ替えます。$y_k$ では $\beta$ が欠けるようになります。$x$ は $P''$ の外なので、$\beta$ は $x$ で欠けたままで、$x$ に接続する辺の色は変わりません。$i<k$ について、$\alpha_i\notin\{\alpha,\beta\}$ なら $y_i$ で欠けたままです。$\alpha_i\in\{\alpha,\beta\}$ となるのは (b) から $i=j-1$ だけで、$y_{j-1}$ は $P$ の頂点で $P''$ の外なので、$\alpha_{j-1}=\alpha$ も $y_{j-1}$ で欠けたままです。したがって、$y_0,\dots,y_k$ と色 $\alpha_0,\dots,\alpha_{k-1},\beta$ は、最後の色 $\beta$ が $x$ で欠けている扇です。場合 1 のとおりにずらせば、$G$ の辺彩色になります。
</Proof>

$\chi'=\Delta$ のグラフを**クラス 1**、$\chi'=\Delta+1$ のグラフを**クラス 2** と呼びます。二部グラフはクラス 1 です。どちらであるかの判定は、3-正則グラフに限っても NP 完全であることが知られています（Holyer, 1981）。

<Example id="ex-complete-graph-edge-colouring" title="完全グラフの辺彩色と総当たり戦">
**$n=2k$ が偶数のとき $\chi'(K_n)=n-1$.** 頂点を $\infty$ と $\mathbb{Z}/(2k-1)\mathbb{Z}$ の元とします。色も $\mathbb{Z}/(2k-1)\mathbb{Z}$ の元とし、辺 $\{\infty,i\}$ に色 $i$ を、辺 $\{a,b\}$（$a\ne b$）に色 $(a+b)/2$ を塗ります（$2k-1$ は奇数なので、$2$ で割ることができます）。色 $i$ の辺は、$\{\infty,i\}$ と、$a+b=2i$ となる組 $\{a,b\}=\{i-j,i+j\}$（$j=1,\dots,k-1$）です。写像 $a\mapsto2i-a$ は、固定点が $i$ だけの対合なので、これらの組は $i$ 以外の元をちょうど 1 回ずつ覆います。よって色クラスは完全マッチングで、$2k-1=\Delta$ 色の辺彩色です。

これは $2k$ チームの総当たり戦の日程です。第 $i$ 日に色 $i$ の辺の対戦を組めば、$2k-1$ 日で全対戦が終わり、毎日全チームが試合をします。

**$n=2k+1$ が奇数のとき $\chi'(K_n)=n$.** 色クラスはマッチングで、辺は $k$ 本以下です。辺は全部で $k(2k+1)$ 本なので、$2k+1$ 色以上が必要です。$K_{2k+2}$ の $2k+1$ 色の辺彩色から 1 頂点を除けば、$2k+1$ 色で塗れます。$\Delta=2k$ なので、奇数頂点の完全グラフはクラス 2 です。
</Example>

<Example id="ex-petersen-edge" title="Petersen グラフはクラス 2">
Petersen グラフ（<Ref to="ex-petersen-chi" /> の記法）は 3-正則で、<Ref to="thm-vizing" /> から $\chi'\le4$ です。$\chi'=3$ ではないことを示します。

3 色 $a,b,c$ の辺彩色があるとします。外側の五角形の 5 辺について、各色の辺はマッチングなので 2 本以下で、$5=2+2+1$ と分かれます。1 本だけの色を $c$ とします。回転 $i\mapsto i+1$、$i+5\mapsto i+6$（5 を法とする）は Petersen グラフの自己同型なので、色 $c$ の辺は $40$ としてよく、残りの $01,12,23,34$ は 2 色が交互に並ぶので、$01$ の色を $a$ として $a,b,a,b$ です。

各頂点には 3 色がちょうど 1 回ずつ現れるので、スポークの色が決まります。頂点 $0$（外側の辺の色は $c,a$）から $05$ は $b$、頂点 $1$（$a,b$）から $16$ は $c$、頂点 $2$（$b,a$）から $27$ は $c$、頂点 $3$（$a,b$）から $38$ は $c$、頂点 $4$（$b,c$）から $49$ は $a$ です。

内側の頂点 $5$ に接続する辺は $05$（色 $b$）、$57$、$58$ なので、$57$ と $58$ の色は $a$ と $c$ です。頂点 $7$ には色 $c$ のスポーク $27$ があるので、$57$ は $a$、したがって $58$ は $c$ です。ところが頂点 $8$ にも色 $c$ のスポーク $38$ があり、矛盾です。よって $\chi'=4=\Delta+1$ です。
</Example>

## 6. 彩色多項式

### 6.1. 除去と縮約

彩色が「できるか」ではなく「何通りあるか」を数えます。

<Definition id="def-chromatic-polynomial" title="彩色の個数">
整数 $k\ge0$ に対し、色集合 $\{1,\dots,k\}$ による $G$ の彩色の個数を $P(G,k)$ と書く。
</Definition>

$\chi(G)$ は $P(G,k)>0$ となる最小の $k$ です。辺のないグラフでは $P=k^n$、完全グラフでは頂点を順に塗って $P(K_n,k)=k(k-1)\cdots(k-n+1)$ です。

辺 $e=uv$ の縮約 $G/e$ は、$u$ と $v$ を 1 頂点にまとめ、多重になった辺を 1 本にしたグラフです（<Ref to="mathematics/graph-theory/kuratowski-theorem#def-minor" />）。

<Theorem id="thm-chromatic-polynomial" title="彩色多項式">
$G$ を $n\ge1$ 頂点、$m$ 辺のグラフとする。

1. どの辺 $e$ についても、すべての整数 $k\ge0$ で $P(G,k)=P(G-e,k)-P(G/e,k)$ が成り立つ。
2. 整数 $a_0,\dots,a_n\ge0$ で、$a_n=1$、$a_{n-1}=m$ であり、すべての整数 $k\ge0$ について
$$
P(G,k)=\sum_{i=0}^{n}(-1)^{n-i}a_i\,k^i
$$
となるものがただ 1 組ある。すなわち $P(G,k)$ は $k$ の $n$ 次のモニック多項式で、係数の符号は交代する。
</Theorem>

この多項式を $G$ の**彩色多項式**といいます。

<Proof of="thm-chromatic-polynomial">
1: $e=uv$ とします。$G-e$ の彩色 $c$ を、$c(u)\ne c(v)$ のものと $c(u)=c(v)$ のものに分けます。前者はちょうど $G$ の彩色です。後者は、まとめた頂点に共通の色を塗ることで $G/e$ の彩色と一対一に対応します（$G/e$ でまとめた頂点と隣接するのは、$G-e$ で $u$ か $v$ と隣接する頂点です）。よって $P(G-e,k)=P(G,k)+P(G/e,k)$ です。

2: 辺の数 $m$ についての帰納法です。$m=0$ なら $P=k^n$ で、$a_n=1$、他は $0$ です。$m\ge1$ とし、辺 $e$ を取ります。$G-e$ は $n$ 頂点、$m-1$ 辺で、$G/e$ は $n-1$ 頂点、$m-1$ 辺以下なので、帰納法の仮定から
$$
P(G-e,k)=\sum_{i=0}^{n}(-1)^{n-i}b_ik^i,\qquad P(G/e,k)=\sum_{i=0}^{n-1}(-1)^{n-1-i}b_i'k^i
$$
（$b_i,b_i'\ge0$、$b_n=1$、$b_{n-1}=m-1$、$b_{n-1}'=1$）と書けます。1 から
$$
P(G,k)=\sum_{i=0}^{n}(-1)^{n-i}b_ik^i+\sum_{i=0}^{n-1}(-1)^{n-i}b_i'k^i
$$
で、$a_n=b_n=1$、$a_i=b_i+b_i'\ge0$（$i<n$）、$a_{n-1}=(m-1)+1=m$ です。一意性は、次数 $n$ 以下の多項式が $n+1$ 個以上の点での値で決まることから従います。
</Proof>

<Corollary id="cor-tree-cycle-polynomial" title="木と閉路の彩色多項式">
1. $n$ 頂点の木 $T$ について $P(T,k)=k(k-1)^{n-1}$。
2. 長さ $n\ge3$ の閉路 $C_n$ について $P(C_n,k)=(k-1)^n+(-1)^n(k-1)$。
</Corollary>

<Proof of="cor-tree-cycle-polynomial">
1: $n$ についての帰納法です。$n=1$ なら $k$ です。$n\ge2$ の木は葉 $v$ をもちます（<Ref to="mathematics/combinatorics/graphs-and-determinants#lem-forest" />）。$T-v$ は $n-1$ 頂点の木で、その彩色のそれぞれに対し、$v$ にはただ 1 つの隣接点の色以外の $k-1$ 色が使えます。よって $P(T,k)=(k-1)\cdot k(k-1)^{n-2}$ です。

2: $n$ についての帰納法です。$C_3=K_3$ では $P=k(k-1)(k-2)$ で、$(k-1)^3-(k-1)=(k-1)\bigl((k-1)^2-1\bigr)=(k-1)k(k-2)$ と一致します。$n\ge4$ とし、$C_n$ の辺 $e$ を取ります。$C_n-e$ は $n$ 頂点の道（木）、$C_n/e$ は $C_{n-1}$ です。<Ref to="thm-chromatic-polynomial" /> の 1 と帰納法の仮定から
$$
P(C_n,k)=k(k-1)^{n-1}-(k-1)^{n-1}-(-1)^{n-1}(k-1)=(k-1)^n+(-1)^n(k-1)
$$
です。
</Proof>

たとえば $P(C_5,3)=2^5-2=30$ で、五角形の 3 色での塗り方は 30 通りです。$P(C_n,2)=1+(-1)^n$ は、$n$ が偶数なら 2、奇数なら 0 で、奇閉路が 2 色で塗れないことと合っています。

### 6.2. Whitney の展開

<Proposition id="prop-whitney-expansion" title="Whitney の展開">
辺集合 $F\subseteq E(G)$ に対し、全域部分グラフ $(V(G),F)$ の連結成分の個数を $c(F)$ と書く。このとき、すべての整数 $k\ge0$ について
$$
P(G,k)=\sum_{F\subseteq E(G)}(-1)^{|F|}\,k^{c(F)}
$$
が成り立つ。
</Proposition>

<Proof of="prop-whitney-expansion">
$X$ を、$V(G)$ から $\{1,\dots,k\}$ への写像の全体とします（彩色とは限りません）。辺 $e=uv$ に対し $A_e=\{c\in X:c(u)=c(v)\}$ とおくと、彩色とは、どの $A_e$ にも属さない $c$ のことです。包除原理（<Ref to="mathematics/combinatorics/posets-mobius#thm-inclusion-exclusion" />）から
$$
P(G,k)=\Bigl|X\setminus\bigcup_{e}A_e\Bigr|=\sum_{F\subseteq E(G)}(-1)^{|F|}\Bigl|\bigcap_{e\in F}A_e\Bigr|
$$
です（$F=\varnothing$ の項は $|X|$）。$\bigcap_{e\in F}A_e$ は、$F$ のどの辺の両端にも同じ色を与える写像の集合で、それは $(V(G),F)$ の各連結成分の上で定数である写像の集合です（辺をたどって色が等しいことが伝わります）。成分ごとに色を 1 つ選ぶので、その個数は $k^{c(F)}$ です。
</Proof>

<Remark id="rem-bond-lattice" title="Möbius 反転との関係">
同じ式は、頂点集合の分割のうち各ブロックが $G$ で連結なものがなす半順序集合（結合束）の上の Möbius 反転（<Ref to="mathematics/combinatorics/posets-mobius#thm-mobius-inversion" />）としても書けます。「各ブロックの上で定数」である写像の個数 $k^{|\pi|}$ を、「ちょうど $\pi$ のブロックの上で定数で、隣接する異なるブロックの色は違う」写像の個数の和に分け、反転して最小元での値を取り出すと $P(G,k)=\sum_\pi\mu(\hat0,\pi)k^{|\pi|}$ となります。完全グラフの場合が、分割束の Möbius 関数の計算です。
</Remark>

<Example id="ex-coefficients" title="係数から辺の数と三角形の数を読む">
<Ref to="prop-whitney-expansion" /> の和で、$k^{n-2}$ の係数に寄与するのは $c(F)=n-2$ の $F$ です。$c(F)=n-2$ とは、$(V,F)$ の全域森の辺が 2 本であることで、そのような $F$ は「相異なる 2 辺」（符号 $+$）か「三角形の 3 辺」（符号 $-$）です。$|F|\ge4$ なら全域森の辺は 3 本以上になります。したがって、$G$ の三角形の個数を $t$ とすると

$$
P(G,k)=k^n-m\,k^{n-1}+\Bigl(\binom m2-t\Bigr)k^{n-2}-\cdots
$$

です。$K_4$ から 1 辺を除いたグラフ（$n=4$、$m=5$、三角形 2 個）では、2 つの三角形が共有する辺の両端を先に塗り、残りの 2 頂点を塗ると $P=k(k-1)(k-2)^2=k^4-5k^3+8k^2-4k$ で、$k^2$ の係数は $\binom52-2=8$ です。
</Example>

<Example id="ex-sudoku" title="数独">
数独の 81 個のマスを頂点とし、同じ行、同じ列、同じ $3\times3$ のブロックにある 2 マスを辺で結びます。各マスは、同じ行の 8 マス、同じ列の 8 マス、同じブロックで行も列も違う 4 マスの、合わせて 20 マスと隣接するので、このグラフは 20-正則です。完成した盤面は 9-彩色で、問題は「一部の頂点の色が決まっているとき、それを彩色に延長せよ」という問題です。行の 9 マスはクリークなので $\omega=9$、盤面が存在するので $\chi=9$ です。あらかじめ色の決まった頂点がある彩色の延長は、次の節のリスト彩色の特別な場合です（決まった頂点はリストが 1 色、その他は 9 色）。
</Example>

## 7. リスト彩色

### 7.1. 定義

<Definition id="def-list-colouring" title="リスト彩色・リスト彩色数">
各頂点 $v$ に色の有限集合 $L(v)$（**リスト**）が与えられているとき、彩色 $c$ ですべての $v$ について $c(v)\in L(v)$ となるものを **$L$-彩色**という。どの頂点のリストも $k$ 色以上であるようなどんな $L$ に対しても $L$-彩色があるとき、$G$ は **$k$-リスト彩色可能**であるという。そのような最小の $k$ を**リスト彩色数** $\operatorname{ch}(G)$ という。
</Definition>

すべてのリストを $\{1,\dots,k\}$ にすれば普通の $k$-彩色なので、$\chi(G)\le\operatorname{ch}(G)$ です。上からは、<Ref to="prop-greedy-bound" /> の証明がそのまま使えます。あの順序で、各頂点に「リストの色のうち、塗り終えた隣接点に使われていないもの」を塗れば、リストが $1+\max_H\delta(H)$ 色以上あるかぎり行き詰まりません。したがって

$$
\chi(G)\le\operatorname{ch}(G)\le1+\max_{H\subseteq G}\delta(H)\le1+\Delta(G)
$$

です。

### 7.2. 平面的グラフは 5-リスト彩色可能

五色定理（<Ref to="mathematics/graph-theory/planar-graphs#thm-five-colour" />）の Kempe 鎖による証明は、リスト彩色にはそのままでは使えません（色の入れ替えがリストからはみ出します）。Thomassen は、帰納法が回るように主張を強めることで、Kempe 鎖を使わない短い証明を見つけました。

辺がすべて線分の平面グラフ $G$ と、その閉路 $C$ の組で、

- $\mathbb{R}^2\setminus C$ の非有界な成分は $G$ の点を含まず（したがって外面で、その境界は $C$。<Ref to="mathematics/graph-theory/kuratowski-theorem#lem-face-region" />）、
- 内面の境界はすべて長さ 3 の閉路である

ものを、**外周 $C$ の三角形分割**と呼ぶことにします。

次の補題のねらいは、「平面的グラフは 5-リスト彩色可能」を帰納法で示せるように、主張を強めておくことです。外周の隣り合う 2 頂点の色をあらかじめ決め、外周のほかの頂点には 3 色、内部の頂点には 5 色のリストを与えます。外周に弦（外周上の 2 頂点を結ぶ辺）があれば、弦で 2 つの小さい三角形分割に切って、それぞれに帰納法の仮定を使います。弦がなければ、外周の頂点 $v_p$ を取り除き、その隣接点のリストから 2 色を減らして帰納法の仮定を使います。

<Lemma id="lem-thomassen" title="三角形分割のリスト彩色（Thomassen）">
$G$ を外周 $C=v_1v_2\cdots v_pv_1$ の三角形分割とする。相異なる色 $c_1,c_2$ と、$v_1,v_2$ 以外の頂点のリスト $L(v)$ が与えられ、

- $C$ の上の頂点 $v\ne v_1,v_2$ では $|L(v)|\ge3$、
- $C$ の上にない頂点 $v$ では $|L(v)|\ge5$

であるとする。このとき、$c(v_1)=c_1$、$c(v_2)=c_2$ で、他の頂点では $c(v)\in L(v)$ となる $G$ の彩色 $c$ が存在する。
</Lemma>

<Proof of="lem-thomassen">
頂点数 $|G|$ についての帰納法です（<Ref to="mathematics/foundations/proof-techniques#thm-strong-induction" />）。$|G|=3$ なら $G=C$ は三角形で、$v_3$ に $L(v_3)\setminus\{c_1,c_2\}$ の色を塗ります。$|G|\ge4$ とします。

**場合 1: $C$ が弦 $uw$ をもつ.** 弦は端点以外で $C$ と交わらず、$C$ の外部は $G$ の点を含まないので、弦の内点は $C$ の内部にあります。$C$ の $u$ から $w$ への 2 本の道を $Q_1,Q_2$ とし、辺 $v_1v_2$ が $Q_1$ にあるとして、$C_i=Q_i\cup uw$ とおきます。平面グラフ $C\cup uw$ の面は、境界が $C$、$C_1$、$C_2$ の 3 つです（<Ref to="mathematics/graph-theory/kuratowski-theorem#lem-theta-faces" />）。境界が $C$ の面は $C$ の外部で、残りの 2 つ $R_1,R_2$（境界は $C_1,C_2$）は、<Ref to="mathematics/graph-theory/kuratowski-theorem#lem-face-region" /> により $C_1$、$C_2$ の内部です。

$G$ の頂点と辺のうち、$R_i\cup C_i$ に含まれるものからなる部分グラフを $G_i$ とします。$G$ の頂点は $C$ の上か $R_1\cup R_2$ にあります。$C\cup uw$ の辺でない $G$ の辺は、端点を除くと連結で $C\cup uw$ と交わらないので、$R_1$ か $R_2$ に含まれ、端点とともに $G_1$ か $G_2$ に属します。よって $G=G_1\cup G_2$ で、共有するのは $u,w$ と辺 $uw$ だけです。$G_i$ は外周 $C_i$ の三角形分割です。実際、$C_i$ の外部は $G_i$ の点を含まず、$G_i$ の内面は $R_i\setminus G$ の連結成分、すなわち $R_i$ に含まれる $G$ の面なので、境界は三角形です。$Q_1,Q_2$ はどちらも内点をもつので、$|G_i|<|G|$ です。

帰納法の仮定を $G_1$ に使い（$v_1,v_2$ は $C_1$ の上で隣り合います）、彩色 $c$ を得ます。$u,w$ は隣接するので $c(u)\ne c(w)$ です。次に $G_2$ に、$u,w$ を「あらかじめ色の決まった隣り合う 2 頂点」として帰納法の仮定を使います。$C_2$ の上の他の頂点は $C$ の上にあってリストは 3 色以上、$C_2$ の上にない $G_2$ の頂点は $C$ の上になくリストは 5 色以上です。2 つの彩色は $u,w$ で一致し、$G$ の辺はどれも $G_1$ か $G_2$ の辺なので、合わせたものが求める彩色です。

**場合 2: $C$ が弦をもたない.** $v_p$ に注目します（$p=3$ なら $v_{p-1}=v_2$ です）。$v_p$ のまわりは、小さい円板の中で、$v_p$ から出る辺の本数だけの扇形に分かれます（<Ref to="mathematics/graph-theory/planar-graphs#lem-local-structure" />）。$C$ の 2 辺 $v_pv_1$、$v_pv_{p-1}$ は外面の境界にあり、外面に含まれる扇形はこの 2 辺に挟まれたもの 1 つです（<Ref to="mathematics/graph-theory/planar-graphs#lem-edge-sides" />。$C$ の辺の両側は異なる面なので、2 つあることはありません。<Ref to="mathematics/graph-theory/planar-graphs#lem-face-boundary" />）。そこで $v_p$ の隣接点を、$v_1$ から始めて外面の扇形を通らない向きに

$$
v_1=u_0,\ u_1,\ \dots,\ u_m,\ u_{m+1}=v_{p-1}
$$

と並べます。$u_j$ と $u_{j+1}$ に挟まれた扇形は内面 $t_j$ に含まれ、$t_j$ の境界は辺 $v_pu_j,v_pu_{j+1}$ を含む三角形なので、$u_ju_{j+1}\in E(G)$ で、$t_j$ の境界は三角形 $v_pu_ju_{j+1}$ です。$C$ は弦をもたないので、$u_1,\dots,u_m$ は $C$ の上にありません。

$m\ge1$ です。$m=0$ とすると $v_1v_{p-1}\in E(G)$ です。$p\ge4$ ならこれは $C$ の弦で、仮定に反します。$p=3$ なら $t_0$ の境界が $C$ 自身で、$t_0$ は $C$ の内部全体になり（<Ref to="mathematics/graph-theory/kuratowski-theorem#lem-face-region" />）、$G=C$、$|G|=3$ となって矛盾です。

$G'=G-v_p$ を考えます。$v_p$ に接続する辺を 1 本ずつ除くと、そのたびに両側の面がつながります（<Ref to="mathematics/graph-theory/planar-graphs#lem-edge-sides" /> の 3）。辺 $v_pu_0$ の両側は外面と $t_0$、辺 $v_pu_j$（$1\le j\le m$）の両側は $t_{j-1}$ と $t_j$、辺 $v_pu_{m+1}$ の両側は $t_m$ と外面です。したがって $G'$ の面は、外面と $t_0,\dots,t_m$ と $v_p$ から出ていた辺と点 $v_p$ を合わせた 1 つの面 $F'$ と、$G$ の残りの内面です。$F'$ の閉包に属する $G'$ の点は、$C$ から $v_p$ とその 2 辺を除いた道 $v_1v_2\cdots v_{p-1}$ と、三角形 $t_j$ の辺 $u_ju_{j+1}$ の点です。つまり $F'$ の境界は

$$
C'=v_1u_1u_2\cdots u_mv_{p-1}v_{p-2}\cdots v_2v_1
$$

で、$u_1,\dots,u_m$ が $C$ の上にないので、これは閉路です。$F'$ は非有界なので $C'$ の外部に等しく（<Ref to="mathematics/graph-theory/kuratowski-theorem#lem-face-region" />）、$G'$ の点を含みません。残りの面の境界は三角形です。よって $G'$ は外周 $C'$ の三角形分割で、$v_1,v_2$ は $C'$ の上で隣り合っています。

$|L(v_p)|\ge3$ なので、$L(v_p)\setminus\{c_1\}$ から相異なる 2 色 $s,t$ を選べます。$G'$ のリストを、$L'(u_j)=L(u_j)\setminus\{s,t\}$（$1\le j\le m$）、その他の頂点では $L'=L$ と定めます。$u_j$ は $C$ の上になかったので $|L(u_j)|\ge5$ で、$|L'(u_j)|\ge3$ です。$C'$ の上の頂点のリストは 3 色以上、$C'$ の上にない頂点は $C$ の上にもないのでリストは 5 色以上です。帰納法の仮定から、$G'$ の彩色 $c$ で条件を満たすものがあります。

$v_p$ の隣接点は $v_1,u_1,\dots,u_m,v_{p-1}$ です。$c(v_1)=c_1$ は $s,t$ と異なり、$c(u_j)\in L'(u_j)$ も $s,t$ と異なります。$s,t$ のうち $c(v_{p-1})$ と異なるほうを $v_p$ に塗れば、$G$ の彩色になります。
</Proof>

<Theorem id="thm-thomassen-5-choosable" title="Thomassen の定理">
平面的グラフは 5-リスト彩色可能である。とくに 5-彩色可能である。
</Theorem>

<Proof of="thm-thomassen-5-choosable">
$G$ を平面的グラフ、$L$ を各リストが 5 色以上のリストの割り当てとします。$|G|\le3$ なら、頂点を順に、塗り終えた隣接点（2 個以下）と違う色で塗れます。$|G|\ge4$ とします。<Ref to="mathematics/graph-theory/kuratowski-theorem#prop-triangulated-supergraph" /> により、$G$ を全域部分グラフとして含むグラフ $G'$ と、その凸な描画で、内面の境界がすべて三角形であるものがあります。凸な描画では辺は線分で、外面の境界は閉路 $C$ なので、$G'$ は外周 $C$ の三角形分割です。$C$ の辺 $v_1v_2$ を 1 つ選び、$c_1\in L(v_1)$、$c_2\in L(v_2)\setminus\{c_1\}$ を選びます。<Ref to="lem-thomassen" /> の条件は満たされている（リストはすべて 5 色以上）ので、$G'$ の $L$-彩色があります。それは部分グラフ $G$ の $L$-彩色でもあります。
</Proof>

<Remark id="rem-voigt" title="5 は最良">
四色定理（<Ref to="mathematics/graph-theory/planar-graphs#thm-four-colour" />）は平面的グラフが 4-彩色可能であることを主張しますが、リスト彩色では 4 に下げられません。4-リスト彩色可能でない平面的グラフがあります（Voigt, 1993）。$\chi$ と $\operatorname{ch}$ は、平面的グラフでも実際に食い違います。
</Remark>

### 7.3. 二部グラフでもリスト彩色数は大きくなる

<Proposition id="prop-choosability-bipartite" title="二部グラフのリスト彩色数は有界でない">
$k\ge1$ とし、$N=\binom{2k-1}{k}$ とおく。完全二部グラフ $K_{N,N}$ は $k$-リスト彩色可能でない。したがって $\operatorname{ch}(K_{N,N})>k$ であり、彩色数 2 のグラフのリスト彩色数はいくらでも大きくなる。
</Proposition>

<Proof of="prop-choosability-bipartite">
色集合を $\{1,\dots,2k-1\}$ とします。その $k$ 元部分集合は $N$ 個あります。$K_{N,N}$ の 2 つの側 $A,B$ のそれぞれで、$N$ 個の頂点に $N$ 個の $k$ 元部分集合を 1 つずつリストとして割り当てます。

$L$-彩色 $c$ があると仮定し、$A$ の頂点に使われた色の集合を $S$ とします。$A$ のどの頂点の色もそのリストに属するので、$S$ はどの $k$ 元部分集合とも交わります。$S$ の補集合が $k$ 元以上あれば、その中の $k$ 元部分集合が $S$ と交わらないので、補集合は $k-1$ 元以下、すなわち $|S|\ge(2k-1)-(k-1)=k$ です。そこで $S$ の $k$ 元部分集合 $S'$ を取り、$S'$ をリストにもつ $B$ の頂点 $b$ を考えます。$c(b)\in S'\subseteq S$ なので、$A$ のある頂点 $a$ が同じ色 $c(b)$ で塗られています。$a$ と $b$ は隣接するので、彩色であることに反します。
</Proof>

## 8. パーフェクトグラフ

### 8.1. 定義と例

$\chi\ge\omega$ の等号が、グラフのどの部分でも成り立つグラフを考えます。perfect graph は「完全グラフ」と訳されることもありますが、$K_n$ と紛れるので、この章ではカタカナで書きます。

<Definition id="def-perfect" title="パーフェクトグラフ・弦グラフ・単体的頂点">
グラフ $G$ が**パーフェクト**であるとは、$G$ のどの誘導部分グラフ $H$ についても $\chi(H)=\omega(H)$ が成り立つことをいう。

長さ 4 以上のどの閉路も弦をもつグラフを**弦グラフ**という。頂点 $v$ は、近傍 $N(v)$ がクリークであるとき**単体的**であるという。
</Definition>

二部グラフはパーフェクトです（誘導部分グラフも二部グラフで、辺があれば $\chi=\omega=2$、なければ $\chi=\omega=1$）。長さ 5 以上の奇閉路は $\chi=3$、$\omega=2$ なので、パーフェクトではありません。弦グラフの誘導部分グラフは弦グラフです（誘導部分グラフの閉路は $G$ の閉路で、その弦は誘導部分グラフの辺でもあります）。

<Theorem id="thm-chordal-perfect" title="弦グラフは単体的頂点をもち、パーフェクトである（Dirac）">
1. 弦グラフは単体的頂点をもつ。完全グラフ $K_n$ でない弦グラフは、隣接しない 2 つの単体的頂点をもつ。
2. 弦グラフはパーフェクトである。
</Theorem>

<Proof of="thm-chordal-perfect">
1: 頂点数 $n$ についての帰納法です（<Ref to="mathematics/foundations/proof-techniques#thm-strong-induction" />）。完全グラフではどの頂点も単体的です。$G$ を完全グラフでない弦グラフとし、隣接しない 2 頂点 $a,b$ を取ります。

*極小な分離集合はクリーク.* $V(G)\setminus\{a,b\}$ の部分集合 $S$ で、$a$ と $b$ が $G-S$ の異なる連結成分に属するもの（$V(G)\setminus\{a,b\}$ 自身がそうです）のうち、包含関係について極小なものを取ります。$G-S$ の、$a$ を含む成分の頂点集合を $A$、$b$ を含む成分のそれを $B$ とします。$S$ の各頂点 $s$ は $A$ にも $B$ にも隣接点をもちます（たとえば $A$ に隣接点をもたなければ、$S\setminus\{s\}$ を除いても $a$ の成分は $A$ のままで、極小性に反します）。

相異なる $s,t\in S$ を取ります。$s$ から $t$ への道で、内点が 1 個以上あり、内点がすべて $A$ に属するもの（$A$ は連結で、$s,t$ は $A$ に隣接点をもつので存在します）のうち、最短のものを $P_A$ とします。同様に $P_B$ を取ります。$P_A\cup P_B$ は長さ 4 以上の閉路なので、弦をもちます。$A$ と $B$ を結ぶ辺はないので、弦は $P_A$ の内点と $P_B$ の内点を結びません。$P_A$ の 2 頂点を結ぶ弦が $st$ でなければ、それを使って $P_A$ より短い、内点を $A$ にもつ道が作れてしまいます。$P_B$ も同様です。したがって弦は $st$ で、$s$ と $t$ は隣接します。$S$ はクリークです。

*単体的頂点.* $G_A=G[A\cup S]$ は弦グラフで、$B\ne\varnothing$ なので頂点数は $n$ 未満です。$G_A$ が完全グラフなら、$A$ の任意の頂点を $a'$ とします。完全グラフでなければ、帰納法の仮定から隣接しない 2 つの単体的頂点をもち、$S$ はクリークなので、その少なくとも一方は $A$ にあります。それを $a'$ とします。どちらの場合も、$a'\in A$ は $G_A$ で単体的です。$a'$ の $G$ での隣接点は $A\cup S$ に属するので、$a'$ は $G$ でも単体的です。同様に、$G[B\cup S]$ から $G$ で単体的な $b'\in B$ が得られます。$A$ と $B$ を結ぶ辺はないので、$a'$ と $b'$ は隣接しません。

2: 弦グラフの誘導部分グラフは弦グラフなので、弦グラフ $G$ について $\chi(G)\le\omega(G)$ を示せば十分です（逆向きは <Ref to="prop-greedy-bound" />）。$n$ についての帰納法です。$n=1$ では $\chi=\omega=1$ です。$n\ge2$ とし、1 から単体的頂点 $v$ を取ります。$N(v)\cup\{v\}$ はクリークなので $|N(v)|\le\omega(G)-1$ です。$G-v$ は弦グラフなので、帰納法の仮定から $\omega(G-v)\le\omega(G)$ 色で彩色できます。$v$ の隣接点に現れる色は $\omega(G)-1$ 色以下なので、$\omega(G)$ 色のうち残っている色を $v$ に塗れます。
</Proof>

<Example id="ex-interval-graph" title="区間グラフ">
実数の閉区間 $I_1,\dots,I_n$ を頂点とし、交わる 2 区間を辺で結んだグラフを**区間グラフ**といいます。会議室の予約を区間とすれば、彩色は「時間の重なる予約を別の部屋に入れる」割り当てで、$\chi$ は必要な部屋の最小数です。

区間グラフは弦グラフです。長さ 4 以上の弦のない閉路 $J_1J_2\cdots J_rJ_1$ があるとし、右端が最小の区間を $J_1=[\ell_1,r_1]$ とします。$J_2$ と $J_r$ はどちらも $J_1$ と交わり、右端が $r_1$ 以上なので、点 $r_1$ を含みます。すると $J_2$ と $J_r$ は交わり、$r\ge4$ ではこれは弦になって矛盾します。

したがって <Ref to="thm-chordal-perfect" /> から $\chi=\omega$ です。区間のクリークは共通点をもつ（左端の最大値は、どの区間の右端よりも大きくない）ので、$\omega$ は「1 点を同時に含む区間の最大数」です。部屋は、最も混む瞬間の予約数だけあれば足ります。
</Example>

<Example id="ex-comparability" title="比較可能グラフと Dilworth の定理">
有限半順序集合 $P$ の元を頂点とし、比較可能な 2 元を辺で結んだグラフ $G_P$ を考えます。クリークは鎖、独立集合は反鎖です。Mirsky の定理（<Ref to="mathematics/combinatorics/posets-mobius#prop-mirsky" />）は「$P$ は最長の鎖の長さと同じ個数の反鎖に分割できる」、すなわち $\chi(G_P)=\omega(G_P)$ を述べています。部分集合に制限しても半順序集合なので、$G_P$ はパーフェクトです。

補グラフ $\overline{G_P}$ では、クリークは反鎖、独立集合は鎖で、彩色は鎖への分割です。Dilworth の定理（<Ref to="mathematics/combinatorics/posets-mobius#thm-dilworth" />）は $\chi(\overline{G_P})=\omega(\overline{G_P})$ を述べています。Mirsky の定理は証明が短く、Dilworth の定理は難しいのですが、次の <Ref to="thm-weak-perfect-graph" /> は、前者から後者が一般論として従うことを示しています。
</Example>

### 8.2. 弱パーフェクトグラフ定理

この命題が欲しいのは、パーフェクトであることを、頂点数と $\alpha,\omega$ だけの不等式で言い換えられると、補グラフに移したときに次の定理が直ちに出るからです。十分性の証明の筋は、背理法です。パーフェクトでない最小の例があるとして、独立集合とクリークをそれぞれ $\alpha\omega+1$ 個ずつ、うまく対になるように作ります。独立集合の特性ベクトルが線形独立になり、$n$ 次元空間に $n$ 個より多くの独立なベクトルが入ることになって矛盾します。

<Proposition id="prop-lovasz-inequality" title="パーフェクトグラフの特徴づけ（Lovász）">
グラフ $G$ がパーフェクトであるためには、$G$ の空でないどの誘導部分グラフ $H$ についても
$$
|H|\le\alpha(H)\,\omega(H)
$$
が成り立つことが必要十分である。
</Proposition>

<Proof of="prop-lovasz-inequality">
**必要性.** $H$ を $\omega(H)$ 色で彩色すると、各色クラスは独立集合で $\alpha(H)$ 頂点以下なので、$|H|\le\omega(H)\alpha(H)$ です。

**十分性（Gasparian の証明）.** $|G|$ についての帰納法です。$|G|=1$ のグラフはパーフェクトです。$G$ が不等式の条件を満たすのにパーフェクトでないと仮定します。$G$ の真の誘導部分グラフは、条件を満たし頂点数が小さいので、帰納法の仮定からパーフェクトです。したがって $\chi(G)>\omega(G)$ です。$n=|G|$、$\alpha=\alpha(G)$、$\omega=\omega(G)$ とおきます。

**(i) 空でない独立集合 $U$ について $\chi(G-U)=\omega(G-U)=\omega$.** $G-U$ はパーフェクトなので $\chi(G-U)=\omega(G-U)\le\omega$ です。$\omega(G-U)\le\omega-1$ なら、$G-U$ の彩色に $U$ を新しい色クラスとして足して $\chi(G)\le\omega$ となり、$\chi(G)>\omega$ に反します。

**(ii) 独立集合の族.** 大きさ $\alpha$ の独立集合 $A_0=\{u_1,\dots,u_\alpha\}$ を取ります。各 $j$ について、(i) を $U=\{u_j\}$ に使うと $\chi(G-u_j)=\omega$ なので、$G-u_j$ の $\omega$-彩色を 1 つ固定し、その $\omega$ 個の色クラスを $A_{(j-1)\omega+1},\dots,A_{j\omega}$ とします。こうして $N=\alpha\omega+1$ 個の空でない独立集合 $A_0,A_1,\dots,A_{\alpha\omega}$ が得られます。

**(iii) 大きさ $\omega$ のクリーク $K$ は、$A_0,\dots,A_{\alpha\omega}$ のうちちょうど 1 つとだけ交わらない.** クリークと独立集合は高々 1 頂点しか共有しません。$u_j\notin K$ なら、$K$ は $G-u_j$ の $\omega$ 頂点のクリークで、$\omega$ 個の色クラスのそれぞれとちょうど 1 頂点を共有します。$u_j\in K$ なら、$K\setminus\{u_j\}$ の $\omega-1$ 頂点が相異なる色クラスに入るので、$K$ は $G-u_j$ の色クラスのうちちょうど 1 つとだけ交わりません。$K\cap A_0=\varnothing$ のとき、すべての $j$ で $u_j\notin K$ なので、$K$ は $A_1,\dots,A_{\alpha\omega}$ のすべてと交わり、交わらないのは $A_0$ だけです。$K\cap A_0=\{u_j\}$ のとき、$K$ は $A_0$ と交わり、$l\ne j$ の $G-u_l$ の色クラスすべてと交わり、$G-u_j$ の色クラスのうちちょうど 1 つとだけ交わりません。

**(iv) クリークの族.** 各 $i\in\{0,\dots,\alpha\omega\}$ について、(i) を $U=A_i$ に使うと $\omega(G-A_i)=\omega$ なので、$A_i$ と交わらない大きさ $\omega$ のクリーク $K_i$ があります。(iii) から、$K_i$ は $l\ne i$ のすべての $A_l$ とちょうど 1 頂点を共有します。

**(v) 線形代数.** $V(G)$ で添字づけた $\mathbb{R}^n$ の中で、$A_l$ の特性ベクトルを $\boldsymbol{a}_l$、$K_i$ の特性ベクトルを $\boldsymbol{b}_i$ とすると、標準内積について
$$
\langle\boldsymbol{a}_l,\boldsymbol{b}_i\rangle=|A_l\cap K_i|=\begin{cases}0&(l=i)\\1&(l\ne i)\end{cases}
$$
です。$\boldsymbol{a}_0,\dots,\boldsymbol{a}_{\alpha\omega}$ が線形独立であることを示します。$\sum_l\lambda_l\boldsymbol{a}_l=\boldsymbol{0}$ とし、$s=\sum_l\lambda_l$ とおきます。$\boldsymbol{b}_i$ との内積を取ると $\sum_{l\ne i}\lambda_l=s-\lambda_i=0$ で、すべての $i$ で $\lambda_i=s$ です。足し合わせると $s=Ns$ で、$N\ge2$ なので $s=0$、したがってすべての $\lambda_i=0$ です。

$\mathbb{R}^n$ は $n$ 個の標準基底ベクトルで張られるので、線形独立なベクトルは $n$ 個以下です（<Ref to="mathematics/linear-algebra/vector-spaces#lem-steinitz" />）。よって $\alpha\omega+1=N\le n$ となり、$H=G$ での条件 $n\le\alpha\omega$ に反します。
</Proof>

<Theorem id="thm-weak-perfect-graph" title="弱パーフェクトグラフ定理（Lovász）">
グラフ $G$ がパーフェクトであることと、補グラフ $\overline G$ がパーフェクトであることは同値である。
</Theorem>

<Proof of="thm-weak-perfect-graph">
$\overline G$ の誘導部分グラフは、$G$ の誘導部分グラフ $H$ の補グラフ $\overline H$ です。$|\overline H|=|H|$、$\alpha(\overline H)=\omega(H)$、$\omega(\overline H)=\alpha(H)$ なので、<Ref to="prop-lovasz-inequality" /> の条件「すべての $H$ で $|H|\le\alpha(H)\omega(H)$」は、$G$ について成り立つことと $\overline G$ について成り立つことが同じです。同じ命題から、$G$ がパーフェクトであることと $\overline G$ がパーフェクトであることは同値です。
</Proof>

二部グラフ $G$ に当てはめると、$\overline G$ がパーフェクト、すなわち「$G$ の頂点を覆うのに必要な辺と頂点（$\overline G$ の色クラスは $G$ のクリークで、辺か 1 頂点です）の最小数は $\alpha(G)$ に等しい」となります。これは König–Egerváry の定理と Gallai の恒等式（<Ref to="mathematics/graph-theory/matchings#thm-konig-egervary" />、<Ref to="mathematics/graph-theory/matchings#thm-gallai-identities" />）から得られる等式で、マッチングの理論の最大最小定理がパーフェクトグラフの言葉に収まることが分かります。

<Remark id="rem-strong-perfect" title="強パーフェクトグラフ定理">
長さ 5 以上の奇閉路と、その補グラフは、パーフェクトではありません。Berge は 1961 年に、これが唯一の障害であること、すなわち「$G$ がパーフェクトであるためには、$G$ も $\overline G$ も長さ 5 以上の奇閉路を誘導部分グラフに含まないことが必要十分である」と予想しました。これは Chudnovsky・Robertson・Seymour・Thomas によって証明され（2006 年出版）、**強パーフェクトグラフ定理**と呼ばれています。条件が補グラフについて対称なので、弱パーフェクトグラフ定理を含みます。証明は 150 ページを超える構造定理で、この章の範囲を超えるので、主張だけを紹介します。出典は参考文献の Chudnovsky らの論文です。
</Remark>

## 9. 演習

<Exercise id="exr-wheel-polynomial" difficulty="標準">
中心 $h$ と長さ 4 の閉路 $v_1v_2v_3v_4$ からなる車輪 $W_4$（$h$ は 4 頂点すべてと隣接）の彩色多項式を求め、$\chi(W_4)$ を答えよ。また、$k^3$ の係数を <Ref to="ex-coefficients" /> の公式で検算せよ。
<Solution>
$h$ の色を $k$ 通りに選ぶと、外周の 4 頂点は残りの $k-1$ 色による $C_4$ の彩色でなければなりません。<Ref to="cor-tree-cycle-polynomial" /> から

$$
P(W_4,k)=k\,P(C_4,k-1)=k\bigl((k-2)^4+(k-2)\bigr)=k(k-2)\bigl((k-2)^3+1\bigr).
$$

$x^3+1=(x+1)(x^2-x+1)$ に $x=k-2$ を入れると $(k-2)^3+1=(k-1)(k^2-5k+7)$ なので

$$
P(W_4,k)=k(k-1)(k-2)(k^2-5k+7)=k^5-8k^4+24k^3-31k^2+14k.
$$

展開は $(k^3-3k^2+2k)(k^2-5k+7)=k^5-5k^4+7k^3-3k^4+15k^3-21k^2+2k^3-10k^2+14k$ です。$P(W_4,2)=0$、$P(W_4,3)=3\cdot2\cdot1\cdot1=6>0$ なので $\chi(W_4)=3$ です。

検算: $n=5$、$m=8$ で、三角形は $hv_iv_{i+1}$ の 4 個です。$k^4$ の係数は $-m=-8$、$k^3$ の係数は $\binom82-4=24$ で、合っています。
</Solution>
</Exercise>

<Exercise id="exr-round-robin" difficulty="易">
6 チームの総当たり戦を 5 日で終える日程を、<Ref to="ex-complete-graph-edge-colouring" /> の構成で具体的に書け。
<Solution>
チームを $\infty,0,1,2,3,4$ とし、第 $i$ 日（$i\in\mathbb{Z}/5\mathbb{Z}$）に $\{\infty,i\}$、$\{i-1,i+1\}$、$\{i-2,i+2\}$ を対戦させます。

| 日 | 対戦 |
|---|---|
| 0 | $\infty$–0、4–1、3–2 |
| 1 | $\infty$–1、0–2、4–3 |
| 2 | $\infty$–2、1–3、0–4 |
| 3 | $\infty$–3、2–4、1–0 |
| 4 | $\infty$–4、3–0、2–1 |

$\infty$ を含まない対戦 $\{a,b\}$ は $a+b\equiv2i$ となる日 $i$ に 1 回だけ現れます。たとえば $\{1,4\}$ は $1+4=5\equiv0$ から第 0 日、$\{0,3\}$ は $3\equiv2\cdot4$ から第 4 日です。15 対戦がすべて 1 回ずつ現れ、毎日 6 チームすべてが試合をします。
</Solution>
</Exercise>

<Exercise id="exr-k24-choosability" difficulty="標準">
$K_{2,4}$ のリスト彩色数は 3 であることを示せ。
<Solution>
**2-リスト彩色可能でない.** 2 頂点の側を $a_1,a_2$、4 頂点の側を $b_1,\dots,b_4$ とし、リストを
$$
L(a_1)=\{1,2\},\quad L(a_2)=\{3,4\},\quad L(b_1)=\{1,3\},\ L(b_2)=\{1,4\},\ L(b_3)=\{2,3\},\ L(b_4)=\{2,4\}
$$
とします。$a_1$ の色 $s\in\{1,2\}$ と $a_2$ の色 $t\in\{3,4\}$ をどう選んでも、$\{s,t\}$ をリストにもつ $b_j$ があり、その頂点には使える色が残りません。

**3-リスト彩色可能.** $K_{2,4}$ のどの部分グラフにも次数 2 以下の頂点があります（$b_j$ が残っていればその次数は 2 以下で、残っていなければ辺がありません）。したがって $\max_H\delta(H)\le2$ で、7.1 節の評価から $\operatorname{ch}\le3$ です。直接には、$a_1,a_2$ を先にリストの色で塗り、各 $b_j$ に、3 色以上あるリストから $a_1,a_2$ の色を除いた残りの色を塗ればよい。
</Solution>
</Exercise>

<Exercise id="exr-critical-edges" difficulty="標準">
$k\ge2$ とする。彩色数が $k$ のグラフは、辺を少なくとも $\binom k2$ 本もつことを示せ。等号が成り立つのは、孤立点を除いて $K_k$ のときに限ることも示せ。
<Solution>
$\chi(G)=k$ とし、$k$-色臨界な部分グラフ $H$ を取ります。$\chi(H)=k$ なので $|H|\ge k$ で、<Ref to="prop-critical" /> から $\delta(H)\ge k-1$ です。握手補題（<Ref to="mathematics/graph-theory/paths-cycles-trees#lem-handshake" />）から
$$
2|E(G)|\ge2|E(H)|=\sum_{v\in V(H)}d_H(v)\ge|H|(k-1)\ge k(k-1)
$$
で、$|E(G)|\ge\binom k2$ です。

等号が成り立つとします。すると $|H|=k$ で、$H$ のどの頂点も次数がちょうど $k-1$、すなわち $H=K_k$ です。さらに $E(G)=E(H)$ なので、$G$ の辺はすべて $H$ の辺で、$H$ の外の頂点は孤立点です。逆に、$K_k$ に孤立点を足したグラフは彩色数 $k$ で辺が $\binom k2$ 本です。

別の見方: $k$-彩色の色クラスを $V_1,\dots,V_k$ とすると、$\chi=k$ ならどの 2 つの色クラスの間にも辺があります（なければ 2 つをまとめて $k-1$ 色にできます）。組は $\binom k2$ 個あるので、これだけで不等式は従います。
</Solution>
</Exercise>

## 参考文献

- R. Diestel, *Graph Theory*, 5th ed., Graduate Texts in Mathematics 173, Springer, 2017 — 第 5 章（彩色。Brooks・Vizing・リスト彩色・パーフェクトグラフ）。
- L. Lovász, "Three short proofs in graph theory", *Journal of Combinatorial Theory, Series B* 19 (1975), 269–271 — Brooks の定理の証明。
- J. Mycielski, "Sur le coloriage des graphes", *Colloquium Mathematicum* 3 (1955), 161–162.
- C. Thomassen, "Every planar graph is 5-choosable", *Journal of Combinatorial Theory, Series B* 62 (1994), 180–181.
- G. S. Gasparian, "Minimal imperfect graphs: a simple approach", *Combinatorica* 16 (1996), 209–212 — <Ref to="prop-lovasz-inequality" /> の線形代数による証明。
- M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, "The strong perfect graph theorem", *Annals of Mathematics* 164 (2006), 51–229.