彩色数の大きいグラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
最大クリークの大きなグラフは彩色数も大きいが、逆は必ずしも真ではない。Grötzschグラフ(en)は4-彩色的だが、三角形を含まない（クリークがない）。それを一般化したグラフをMycielskianと呼ぶ。 Mycielskiの定理: 三角形を含まない、任意の彩色数のグラフが存在する。 ブルックスの定理から、彩色数の大きいグラフは次数が高くなければならない。また、局所的には大きなクリークがあれば彩色数は大きくなる。しかし、彩色可能性はグラフの局所的現象ではない。内周（最短閉路の長さ）が大きいグラフは、局所的に見れば木のようになっているが、その彩色数は2になるとは限らない。 定理（エルデシュ）: 任意の内周が大きくかつ彩色数の大きいグラフが存在する。
※この「彩色数の大きいグラフ」の解説は、「グラフ彩色」の解説の一部です。
「彩色数の大きいグラフ」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
ウィキペディア小見出し辞書の「彩色数の大きいグラフ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 彩色数の大きいグラフのページへのリンク
