パーフェクトグラフ予想
2008年11月13日 (木) 13:33時点におけるAlbeit-Kun (トーク | 投稿記録)による版
【ぱーふぇくとぐらふよそう (perfect graph conjecture)】
奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である.