彩色指数の境界
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
G の辺彩色は、そのライングラフ L ( G ) {\displaystyle L(G)} の頂点彩色と等価であり、逆も成り立つ。従って、 χ ′ ( G ) = χ ( L ( G ) ) {\displaystyle \chi '(G)=\chi (L(G))\,} 辺彩色可能性とそのグラフの最大次数 Δ ( G ) {\displaystyle \Delta (G)} には強い関連性がある。同じ頂点に接合する全ての辺は異なる色にしなければならないので、次が成り立つ。 χ ′ ( G ) ≥ Δ ( G ) {\displaystyle \chi '(G)\geq \Delta (G)\,} さらに次が成り立つ。 ケーニグの定理: G が2部グラフなら χ ′ ( G ) = Δ ( G ) {\displaystyle \chi '(G)=\Delta (G)} 一般に、この関係はブルックスの定理が頂点彩色に与える関係よりも強い。 Vizingの定理: 最大次数 Δ {\displaystyle \Delta } のグラフの辺彩色数は Δ {\displaystyle \Delta } または Δ + 1 {\displaystyle \Delta +1} である。
※この「彩色指数の境界」の解説は、「グラフ彩色」の解説の一部です。
「彩色指数の境界」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
ウィキペディア小見出し辞書の「彩色指数の境界」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 彩色指数の境界のページへのリンク
