内周とグラフ彩色

ウィキペディア小見出し辞書

内周とグラフ彩色

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/21 16:50 UTC 版)

「内周 (グラフ理論)」の記事における「内周とグラフ彩色」の解説

任意の正の整数 g と χ に対して、内周が少なくとも g であり、彩色数が少なくとも χ であるようなグラフが存在する：例えば、グレッチグラフ（英語版）はトライアングルフリーで彩色数が 4 であり、そのグラフを構成するためのミシェルスキアン（英語版）構成法を繰り返すことで、任意の大きさの彩色数を備えるトライアングルフリーなグラフを構成することが出来る。ポール・エルデシュは、確率的手法（英語版）を用いて、初めてその一般的な結果を証明した。厳密に言うと彼は、各辺が含まれるかどうかが確率 n(1 − g)/g で独立に決定されるような頂点数 n のランダムグラフ（英語版）は、n が無限大へと向かうにつれて 1 に近付くような確率に対して、長さが g 以下であるような閉路を多くとも n/2 個含むが、大きさが n/2k であるような独立集合は含まない、ということを証明した。したがって、それぞれの短閉路（short cycle）から一つ頂点を取り除くことにより、内周が g より大きく、各彩色の同色集合が小さいためにどのような彩色においても少なくとも k 色が必要となるような、より小さいグラフが得られる。