「パーフェクトグラフ予想」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である. | 奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である. | ||
| + | |||
| + | [[Category:組合せ最適化|ぱーふぇくとぐらふよそう]] | ||
2008年11月13日 (木) 13:33時点における最新版
【ぱーふぇくとぐらふよそう (perfect graph conjecture)】
奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である.