パーフェクトグラフ

【ぱーふぇくとぐらふ (perfect graph)】

グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ $G\,$ のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, $G\,$ をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている.