「パーフェクトグラフ予想」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: '【ぱーふぇくとぐらふよそう (perfect graph conjecture)】 奇数個の頂点と同数の辺からなるサイクル(奇ホール(odd hole))の長さが5以上な...')
 
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
【ぱーふぇくとぐらふよそう (perfect graph conjecture)】
+
'''【ぱーふぇくとぐらふよそう (perfect graph conjecture)】'''
  
 
奇数個の頂点と同数の辺からなるサイクル(奇ホール(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以上の奇ホールもその補グラフも含まないならパーフェクトであるという予想である.