彩色と独立集合
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:46 UTC 版)
グラフ理論（英語版）によると、完全グラフ K4 以外のすべての立方体グラフは、多くとも 3色によって彩色される。したがって、K4 以外のすべての立方体グラフは、少なくとも n/3 個の頂点の独立集合を持つことになる。ここで n はそのグラフ内の頂点の数とする：例えば、3-彩色における最大の色の類は、少なくともこのくらい多くの頂点を含む。 ビジングの定理（英語版）によると、すべての立方体グラフは、その辺彩色のために 3色か 4色を必要とする。3-辺彩色はテイト彩色として知られ、そのグラフの辺を三つの完全マッチングへと区分する。ケーニヒの線彩色定理（英語版）によれば、すべての2部立方体グラフにはテイト彩色が存在する。 テイト彩色が存在しない、橋のない立方体グラフはスナーク（英語版）として知られる。ピーターセングラフや、ティーツェのグラフ（英語版）、ブラヌサスナーク（英語版）、フラワースナーク（英語版）、ダブルスタースナーク（英語版）、スゼッケルスナーク（英語版）、ワトキンススナーク（英語版）などが、これに該当する。スナークは無数に存在する。
※この「彩色と独立集合」の解説は、「立方体グラフ」の解説の一部です。
「彩色と独立集合」を含む「立方体グラフ」の記事については、「立方体グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「彩色と独立集合」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 彩色と独立集合のページへのリンク
