パーフェクトグラフ予想

OR事典

パーフェクトグラフ予想

読み方：ぱーふぇくとぐらふよそう
【英】：perfect graph conjecture

奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である.

「OR事典」の他の用語

組合せ最適化：

ネットワークフロー問題  ハッシュ表  パーフェクトグラフ  パーフェクトグラフ予想  ヒープ  ファセット制約  フィボナッチヒープ