彩色数の境界
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
個々の頂点にそれぞれ異なる色を割り当てれば、その彩色は正しい。従って次が成り立つ。 1 ≤ χ ( G ) ≤ n {\displaystyle 1\leq \chi (G)\leq n\,} 1-彩色可能なのは辺のないグラフに限られる。n個の頂点を持つ完全グラフ K n {\displaystyle K_{n}} を彩色するには χ ( K n ) = n {\displaystyle \chi (K_{n})=n} 色が必要である。最適な彩色では、グラフ内の m 個以上の辺が色クラス間を結ぶ位置にある。従って、次が成り立つ。 χ ( G ) ( χ ( G ) − 1 ) ≤ 2 m {\displaystyle \chi (G)(\chi (G)-1)\leq 2m\,} G に大きさ k のクリークが含まれている場合、そのクリークの彩色に少なくとも k 色を必要とする。言い換えれば、グラフ G の彩色数について次が成り立つ。 χ ( G ) ≥ ω ( G ) {\displaystyle \chi (G)\geq \omega (G)\,} 区間グラフでは、この境界がきつい。 2-彩色可能なグラフは常に2部グラフであり、木や森もそれに含まれる。四色定理により、全ての平面グラフは4-彩色可能である。 貪欲彩色法によれば、あらゆるグラフは頂点の最大次数より1つ多い色数で彩色可能である。 χ ( G ) ≤ Δ ( G ) + 1 {\displaystyle \chi (G)\leq \Delta (G)+1\,} 完全グラフは χ ( G ) = n {\displaystyle \chi (G)=n} かつ Δ ( G ) = n − 1 {\displaystyle \Delta (G)=n-1} であり、奇閉路は χ ( G ) = 3 {\displaystyle \chi (G)=3} かつ Δ ( G ) = 2 {\displaystyle \Delta (G)=2} である。したがってこの境界条件はこれらのグラフでは彩色数をよく限定する。それら以外のグラフでは、境界条件をさらに若干改良する余地がある。ブルックスの定理は次の通りである。 ブルックスの定理: 完全グラフでも奇閉路でもない単純な連結グラフ G について χ ( G ) ≤ Δ ( G ) {\displaystyle \chi (G)\leq \Delta (G)} が成り立つ。
※この「彩色数の境界」の解説は、「グラフ彩色」の解説の一部です。
「彩色数の境界」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
- 彩色数の境界のページへのリンク
