「パーフェクトグラフ予想」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【ぱーふぇくとぐらふよそう (perfect graph conjecture)】 奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上な...') |
|||
| 1行目: | 1行目: | ||
| − | 【ぱーふぇくとぐらふよそう (perfect graph conjecture)】 | + | '''【ぱーふぇくとぐらふよそう (perfect graph conjecture)】''' |
奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である. | 奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である. | ||
2007年7月17日 (火) 16:00時点における版
【ぱーふぇくとぐらふよそう (perfect graph conjecture)】
奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上ならば, クリーク数は2で彩色数は3となりパーフェクトグラフではない. さらにその補グラフ(odd antihole)もパーフェクトではない. すなわち, これらを頂点誘導部分グラフとして含むグラフはパーフェクトではない. パーフェクトグラフ予想とは, この逆の命題, 頂点誘導部分グラフとして長さ5以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である.