グラフ彩色 ― 何色あれば塗り分けられるか
彩色数$\chi(G)$，貪欲彩色，Brooksの定理，彩色多項式，辺彩色とVizingの定理，四色定理の概要を体系的に解説する．
1 頂点彩色
定義 1 (頂点彩色).
グラフ の（正常）頂点彩色（proper vertex coloring）とは，写像 であって，隣接する任意の2頂点 （）に対して を満たすものをいう．このとき は -彩色可能（-colorable）であるという．
定義 2 (彩色数).
が -彩色可能であるような最小の を の彩色数（chromatic number）といい， で表す．
例 3.
（完全グラフではすべての頂点が隣接するので 色必要），（偶数長閉路は二部グラフ），（奇数長閉路）．
奇数長閉路は2色では塗り分けられないが，3色あれば十分である：
2 貪欲彩色
定理 4 (貪欲彩色の上界).
任意のグラフ に対して である．ここで は の最大次数．
証明.
頂点を任意の順序 に並べる．貪欲彩色（greedy coloring）を次のように行う： に対して， の既彩色の隣接頂点が使っていない色のうち最小のものを割り当てる． の隣接頂点は高々 個なので，既彩色の隣接頂点が使う色は高々 色．よって の中に必ず使える色が存在する．帰納的にすべての頂点が 色以内で彩色される． □
3 Brooksの定理
定理 5 (Brooksの定理（1941年）).
が連結単純グラフで，完全グラフでも奇数長閉路でもないならば， が成り立つ．
証明.
証明の骨子のみ述べる． とする（ は容易）． が -正則でなければ，次数 の頂点 を最後に塗る順序で貪欲彩色すれば 色で足りる． が -正則の場合， は完全グラフでないので隣接しない2頂点 が存在し， を同じ色に塗ってから BFS 順序で貪欲彩色する構成により 色で彩色できる． □
4 彩色多項式
定義 6 (彩色多項式).
グラフ に対して， の正常 -彩色の数を とする． は の多項式であり，これを の彩色多項式（chromatic polynomial）という．
定理 7 (削除縮約の公式).
のある辺 に対して， を辺 を除いたグラフ， を辺 を縮約したグラフとすると
証明.
の -彩色のうち であるものは の -彩色でもある． であるものは の -彩色と一対一に対応する．よって ． □
例 8.
完全グラフ の彩色多項式は である．木 の 頂点に対しては ．
5 辺彩色とVizingの定理
定義 9 (辺彩色).
グラフ の辺彩色（edge coloring）とは，共通の端点を持つ任意の2辺に異なる色を割り当てることをいう．必要な最小色数を彩色指数（chromatic index） で表す．
各頂点に接する辺はすべて異なる色でなければならないのでは明らかである．
定理 10 (Vizingの定理（1964年）).
単純グラフ に対して
注意 11.
Vizingの定理により，単純グラフはクラス1（）とクラス2（）に二分される．二部グラフはすべてクラス1であることが知られている（Königの定理）．
6 四色定理
定理 12 (四色定理（Appel–Haken, 1976年）).
すべての平面グラフは -彩色可能である．すなわち平面グラフ に対して ．
注意 13.
四色定理は数学史上初めて計算機を本質的に使って証明された定理である．不可避集合（unavoidable set）と可約性（reducibility）の概念を用いた証明は，約1500通りの場合分けを計算機で検証するものであった．1997年にRobertson–Sanders–Seymour–Thomasが簡略化された証明を与え，2005年にはGonthier–Wernerが定理証明支援系 Coq で形式的に検証した．なお，（五色定理）は Kempe 鎖の議論で容易に示される： より次数5以下の頂点 が存在し， を除いて帰納的に5-彩色した後， の隣接頂点が5色すべてを使っている場合に Kempe 鎖の交換で1色空けることができる．