車輪グラフ

車輪グラフ（しゃりんグラフ、英: Wheel graph）とは、グラフ理論のグラフの1つであり、閉路グラフと、そのすべての頂点に接続するユニバーサル頂点（支配頂点）と呼ばれる頂点からなるグラフである。"n" 頂点の車輪グラフは、 "n" - 1角錐の、1-とも定義できる（3 < "n")。"n" 頂点の車輪グラフを"W""n"で表したり、"n" + 1 頂点の車輪グラフを、 "n" 角形で表せることから "W""n"で表したりする。本記事内では、前者の表記を用いる。
内包表記での構成.
頂点集合 {1, 2, 3, …, "v" }に対し辺の集合は内包表記でと表せる。
ここで、頂点1がユニバーサル頂点であり、頂点2から頂点 "v" は閉路グラフを構成する。
性質.
車輪グラフは
"n" が奇数の場合、 "W""n" は彩色数3のパーフェクトグラフである。つまり、ユニバーサル頂点以外の頂点を交互に2色に塗り分け、中央のユニバーサル頂点を3色目で塗り分けられる。"n" が偶数の場合、 "W""n" は彩色数が4であり、"n" ≥ 6 でパーフェクトグラフではなくなる。 "W"7 はユークリッド平面上で唯一単位距離グラフである 
車輪グラフ "Wn" の彩色多項式は、formula_2である。
マトロイドの分野では、特に重要な特殊なクラスに "wheel matroids" と "whirl matroids"　があり、これらは車輪グラフから導かれる。 "k"-wheel マトロイドは、"W""k+1"の閉路マトロイドであり、 "k"-whirl マトロイドは、 wheelマトロイドの外側の閉路とそのすべての全域木が独立しているとみなすことによって、 "k" wheelマトロイドから導かれる。
車輪グラフ "W"6 は、ラムゼー理論におけるポール・エルデシュの予想（下記）の反例となった。
ポール・エルデシュは、「彩色数が同じグラフでは、完全グラフがラムゼー数が最小となるグラフである」と予想した。しかし、Faudree と McKay は1993年に "W"6 はラムゼー数が17であり、同じ彩色数を持つ完全グラフ "K"4　のラムゼー数である18より小さいことを示し、反例とした。つまり、すべての17頂点のグラフ "G"について、 "G"またはその補グラフのどちらかが部分グラフとして "W"6 を含む一方で、17頂点のもその補グラフも完全グラフ "K"4を含まない。