6.3. Brooks の定理

先述したように、与えられたグラフ \(G\) が適切な \(k\)-彩色を持つかどうかを判定する問題は \(k \leq 2\) でない限り計算量的に難しい問題となる。この事実は理論的な判定基準を考える場合でも変わらない: \(k > 2\) のとき、グラフに適切な \(k\)-彩色が存在するための必要十分条件となる優れた判定基準を私は知らない。ただし、十分条件はいくつか知られている。その一つを次に示す:

[証明 (概略)] \(G\) の頂点を適当な順番で \(v_{1},v_{2},\ldots,v_{n}\) とする。\(G\) の適切な \(\left( \alpha+1\right) \)-彩色 \(f\colon V\rightarrow\left\{ 1,2,\ldots,\alpha +1\right\} \) を、次のように再帰的に構築する:

• まず、\(f\left( v_{1}\right) \) を任意に選ぶ。

• 次に \(f\left( v_{2}\right) \) を選ぶ。\(v_{2}\) のどの隣接頂点の色とも異なる色を \(f\left( v_{2}\right) \) とする。

• 次に \(f\left( v_{3}\right) \) を選ぶ。\(v_{3}\) のどの隣接頂点の色とも異なる色を \(f\left( v_{3}\right) \) とする。

• 次に \(f\left( v_{4}\right) \) を選ぶ。\(v_{4}\) のどの隣接頂点の色とも異なる色を \(f\left( v_{4}\right) \) とする。

• 同じことを \(f\left( v_{1}\right) ,\ f\left( v_{2}\right) ,\ \ldots,\ f\left( v_{n}\right) \) が全て定まるまで繰り返す。

この構築において、任意の頂点を塗る色が常に存在すると言えるのはなぜだろうか？ 理由は次の通りである: \(f\left( v_{i}\right) \) の色を選ぶときは、\(v_{i}\) の隣接頂点の中でこれまでに色の塗られたものと異なる色を選ぶ必要がある。\(\alpha\) の定義より、\(v_{i}\) の隣接頂点の個数は \(\alpha\) 以下である。色の選択肢は \(\alpha + 1\) 個あるから、少なくとも一つの色は必ず選べる。つまり色が足りなくなることはない。

こうして構築される \(\left( \alpha+1\right) \)-彩色 \(f\colon V\rightarrow\left\{ 1,2,\ldots,\alpha+1\right\} \) を貪欲彩色 (greedy coloring) と呼ぶ。貪欲彩色は適切である: 任意の辺の端点を \(v_{i}\), \(\,v_{j}\) (\(i > j\)) とするとき、\(f\left( v_{i}\right) \) の構築が \(f\left( v_{i}\right) \neq f\left( v_{j}\right) \) を保証する。 [ここで \(G\) がループレスである事実が使われていることに注意せよ！ ループの端点を \(v_{i}\), \(v_{j}\) とするとき \(i>j\) は成り立たない。] □

一般に定理 6.3.1 の \(\alpha + 1\) は改善できない。この事実が分かる例を二つ示す:

• 任意の \(n \geq 2\) に対する閉路グラフ² \(C_{n}\) では \(\alpha=\max\left\{ \deg v\mid v\in V\right\} =2\) なので、定理 6.3.1 から \(C_{n}\) が適切な \(3\)-彩色を持つと分かる。\(n\) が偶数のとき \(C_{n}\) は適切な \(2\)-彩色を持つものの、\(n\) が奇数のとき \(C_{n}\) は適切な \(2\)-彩色を持たない (定理 6.2.1 より)。

• 任意の \(n\geq1\) に対する完全グラフ \(K_{n}\) では \(\alpha=\max\left\{ \deg v\mid v\in V\right\} =n-1\) なので、定理 6.3.1 から \(K_{n}\) が適切な \(n\)-彩色を持つと分かる。しかし \(K_{n}\) が適切な \(n-1\)-彩色を持たないことは鳩の巣原理より明らかである。

興味深いことに、最大次数が \(\alpha\) であって適切な \(\alpha\)-彩色を持たない連結でループレスなグラフはここに示した二種類しか存在しない。他の全ての場合において、定理 6.3.1 の \(\alpha + 1\) は \(\alpha\) に改善できる:

[証明] この定理は一見すると定理 6.3.1 とそれほど変わらないものの、その証明は格段に難しい。[CraRab15] やグラフ理論の専門的な教科書を見れば様々な証明を確認できる。