完全グラフ
定義
グラフ $G$ の全ての 誘導された サブ グラフ $H$ が次を満たすとき、完全グラフという。 $$ \chi (H) = \omega (H) $$
説明
グラフ理論の世界は、多くの数学の分科がそうであるように、途方もなく広い、正直もう少し広いと言いたい。グラフで頂点とエッジを定義する方法があまりにも多様だからだ。路線グラフはもちろん、区間グラフのように、グラフである必要がなかったものでもグラフはグラフである。
ただ、それが価値があるかどうかは別の問題だ。グラフの研究で価値があると考えられる場合は、グラフ彩色や連結性、距離的性質などに関する内容が最も簡単に思いつくだろう。単にグラフが定義されただけでは、大きな注目を浴びるのは難しい。
完全グラフは、グラフ彩色に特に興味を持つ意味で、完璧なグラフと見なすことができる。すべてのグラフ $H$ は、クリーク数 $\omega (H)$ に対して当然 $$ \omega (H) \le \chi (H) $$ どんなグラフでも、サブクリーク $K_{n}$ が存在するなら、当然 $n-1$ 色で彩色できないからだ。完全グラフは、不等号が適用される場合を除外したもので、クリーク以外は必ずより少ない色で彩色できる。
純粋なグラフ理論は組み合わせ論の一つの分野と見なされ、組み合わせの問題では、このような完全グラフのような概念が必ず登場する。