ブルックスの定理

3行要約

1. グラフの彩色数に関する定理で、最大次数をΔとしたとき、彩色数は高々Δである。
2. 完全グラフと奇サイクルという2つの例外を除き、Δ色あれば隣接頂点を塗り分けられる。
3. グラフ理論における頂点彩色の限界を明示した、基本的かつ重要な成果。