強い完全グラフ定理

グラフ理論において、強パーフェクトグラフ定理は、奇数ホール（長さが5以上の奇数長の誘導サイクル）も奇数反ホール（奇数ホールの補数）も持たないグラフをパーフェクトグラフとする禁制グラフの特徴付けである。これは1961年にクロード・ベルジュによって予想された。マリア・チャドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマスによる証明は2002年に発表され^[1]、2006年に彼らによって出版された。

強完全グラフ定理の証明により、その著者らはカーネギーメロン大学のジェラール・コルヌエジョルス氏から1万ドルの賞金^[2]と2009年のフルカーソン賞を獲得した。^[3]

パーフェクトグラフは、すべての誘導部分グラフについて、最大クリークのサイズがグラフの色分けにおける最小の色数に等しいグラフである。パーフェクトグラフには、二部グラフ、弦グラフ、比較可能性グラフなど、多くのよく知られたグラフクラスが含まれる。1961年と1963年に初めてこのグラフクラスを定義した研究で、クロード・ベルジュは、パーフェクトグラフが奇数ホール（長さが5以上である奇数長サイクルグラフの形の誘導部分グラフ）を含むことは不可能であると指摘した。これは、奇数ホールのクリーク数が2で彩色数が3であるためである。同様に、彼は、パーフェクトグラフが奇数アンチホール（奇数ホールの補完的な誘導部分グラフ）を含むことはできないと指摘した。2 k  + 1 個の頂点を持つ奇数アンチホールはクリーク数がkで彩色数がk  + 1 であるが、これもパーフェクトグラフでは不可能である。奇数ホールも奇数アンチホールも持たないグラフは、ベルジュグラフとして知られるようになった。

ベルジュは、すべてのベルジュ グラフは完全である、または同等に、完全グラフとベルジュ グラフは同じグラフのクラスを定義すると予想しました。これは、2002 年に証明されるまで、強完全グラフ予想として知られていましたが、その後、強完全グラフ定理と改名されました。

ベルゲのもう一つの予想は、1972年にラースロー・ロヴァースによって証明されたが、あらゆるパーフェクトグラフの補グラフもまたパーフェクトであるというものである。これはパーフェクトグラフ定理、または（強パーフェクトグラフ予想/定理と区別するために）弱パーフェクトグラフ定理として知られるようになった。ベルゲの禁制グラフの特徴付けは自己補的であるため、弱パーフェクトグラフ定理は強パーフェクトグラフ定理から直接導かれる。

Chudnovsky らによる強いパーフェクトグラフ定理の証明は、Conforti、Cornuéjols、Robertson、Seymour、および Thomas が 2001 年に推測した概要に従っています。それによると、すべての Berge グラフは、5 種類の基本的な構成要素 (パーフェクトグラフの特別なクラス) のいずれかを形成するか、より単純なグラフへの 4 種類の構造分解のいずれかを持ちます。最小限の不完全な Berge グラフはこれらの分解のいずれも持つことができないため、定理に対する反例は存在しないことになります。 ^[4]このアイデアは、強いパーフェクトグラフ予想を暗示していたが誤りであることが判明した、以前に推測された同様のタイプの構造分解に基づいています。^[5]

この構造分解の基本ケースを形成する 5 つの基本クラスは、二部グラフ、二部グラフの線グラフ、二部グラフの補グラフ、二部グラフの線グラフの補グラフ、および二重分割グラフです。二部グラフが完全であることは簡単にわかります。任意の非自明な誘導サブグラフでは、クリーク数と彩色数は両方とも 2 であり、したがって等しいです。二部グラフの補グラフの完全性と二部グラフの線グラフの補グラフの完全性は、両方とも、二部グラフの最大マッチング、最大独立集合、および最小頂点カバーのサイズに関するケーニッヒの定理と同等です。二部グラフの線グラフの完全性は、ケーニッヒ (1916) によって証明された、二部グラフの彩色指数が最大次数に等しいという事実と同等に述べることができます。したがって、これら 4 つの基本クラスはすべて完全です。二重分割グラフは、分割グラフの相対的なものであり、これも完全であることが示されます。^[6]

この証明で考慮される 4 種類の分解は、2 結合、2 結合の補数、バランスのとれた歪曲分割、および同種ペアです。

2-結合とは、グラフの頂点を 2 つの部分集合に分割することであり、これら 2 つの部分集合間のカットにまたがる辺は、2 つの頂点が互いに素な完全二部グラフを形成するという性質を持つ。グラフに 2-結合がある場合、2 つの部分集合の頂点の 1 つを、その部分集合内で 2 つの完全二部グラフの 1 つをもう 1 つに接続する最短経路で置き換えることで、「ブロック」と呼ばれる誘導部分グラフに分解できる。そのような経路が存在しない場合は、代わりに 2 つの部分集合の頂点の 1 つを、完全二部グラフごとに 1 つずつ、2 つの頂点で置き換えることでブロックが形成される。2-結合が完全であるのは、その 2 つのブロックが両方とも完全である場合に限る。したがって、極小不完全グラフに 2-結合がある場合、それはそのブロックの 1 つに等しいはずであり、したがって、それは奇数サイクルであってベルジュではないことが分かる。同じ理由で、補グラフに2結合を持つ最小不完全グラフはベルゲグラフにはなり得ない。^[7]

歪分割とは、グラフの頂点を 2 つの部分集合に分割することであり、そのうちの 1 つは切断された部分グラフを誘導し、もう 1 つは切断された補集合を持つ。Chvátal (1985) は、強完全グラフ予想に対する最小の反例には歪分割は存在しないと予想した。Chudnovsky らは歪分割にいくつかの技術的制約を導入し、結果として得られる「バランスのとれた歪分割」に対して Chvátal の予想が正しいことを示すことができた。完全な予想は、強完全グラフ定理の帰結である。^[8]

同次対はグラフのモジュラー分解に関連している。これはグラフを3つの部分集合V ₁、V ₂、V ₃に分割したもので、V ₁とV ₂を合わせると少なくとも3つの頂点が含まれ、V _{3 に}は少なくとも2つの頂点が含まれ、V ₃の 各頂点vと{1,2} の各iは、 vがV _iのすべての頂点に隣接しているか、どの頂点にも隣接していないかのいずれかである。最小限の不完全グラフが同次対を持つことは不可能である。^[9]強い完全グラフ予想の証明に続いて、Chudnovsky (2006) は証明で使用される分解の集合から同次対を除去できることを示してそれを簡略化した。

すべてのベルジュグラフが5つの基本クラスのいずれかに分類されるか、または4つの分解タイプのいずれかを持つことの証明は、グラフ内に特定の構成が存在するかどうかによるケース分析に従います。「ストレッチャー」は、特定の追加制約の対象となる3つの誘導パスに分解できるサブグラフ、ストレッチャーの補グラフ、および「適切なホイール」は、ホイールグラフに関連する構成で、誘導サイクルと、少なくとも3つのサイクル頂点に隣接するハブ頂点で構成され、いくつかの追加制約に従います。特定のベルジュグラフ内にストレッチャーまたはその補グラフまたは適切なホイールが存在するかどうかの可能な選択ごとに、グラフが基本クラスのいずれかに分類されるか、分解可能であることが示されます。^[10]このケース分析で証明が完了します。

• Berge、Claude (1961)、「Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind」、Wiss。 Z. マーティン・ルター大学ハレ・ヴィッテンベルクの数学-自然。令河、10 : 114。
• ベルジュ、クロード(1963)、「完全グラフ」、グラフ理論に関する 6 つの論文、カルカッタ: インド統計研究所、pp. 1–21。
• チュドノフスキー、マリア(2006)、「ベルゲ トライグラフ」、グラフ理論ジャーナル、53 (1): 1–55、doi :10.1002/jgt.20165、MR  2245543。
• チュドノフスキー、マリア;ロバートソン、ニール;シーモア、ポール;トーマス、ロビン(2006)、「強い完全グラフ定理」、Annals of Mathematics、164 (1): 51–229、arXiv : math/0212070、doi :10.4007/annals.2006.164.51、MR  2233847。
• マリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマス(2003)、「完全グラフの進歩」、数学プログラミング、シリーズ B、97 (1–2): 405–422、CiteSeerX  10.1.1.137.3013、doi :10.1007/s10107-003-0449-8、MR  2004404。
• Chvátal, Václav (1985)、「スターカットセットとパーフェクトグラフ」、Journal of Combinatorial Theory、シリーズ B、39 (3): 189–199、doi :10.1016/0095-8956(85)90049-8、MR  0815391。
• Chvátal, Václav ; Sbihi, Najiba (1987)、「Bull-free Berge グラフは完全である」、Graphs and Combinatorics、3 (2): 127–139、doi :10.1007/BF01788536、MR  0932129。
• コルヌエジョル、ジェラール(2002)、「強い完全グラフ予想」、国際数学者会議紀要、第 3 巻 (北京、2002) (PDF)、北京: 高等教育出版、pp. 547–559、MR  1957560。
• コルヌエジョルス、G. ; カニンガム、WH (1985)、「完全グラフの合成」、離散数学、55 (3): 245–254、doi : 10.1016/S0012-365X(85)80001-7、MR  0802663。
• Hougardy, S. (1991)、「完全グラフに関する3つの予想に対する反例」、技術レポート RR870-M、グルノーブル、フランス：Laboratoire Artemis-IMAG、Universitá Joseph Fourier。 Roussel、Rusu & Thuillier (2009) が引用したとおり。
• Kőnig、Dénes (1916)、「Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére」、Matematikai és Természettudományi Értesítő、34 : 104–119。
• ロヴァース、ラースロー（1972a）、「正規ハイパーグラフと完全グラフ予想」、離散数学、2（3）：253–267、doi：10.1016/0012-365X（72）90006-4。
• ロヴァース、ラースロー(1972b)、「完全グラフの特徴付け」、組合せ理論ジャーナル、シリーズ B、13 (2): 95–98、doi :10.1016/0095-8956(72)90045-7。
• マッケンジー、ダナ (2002 年 7 月 5 日)、「数学: グラフ理論が完全性の根源を明らかにする」、サイエンス、297 (5578): 38、doi :10.1126/science.297.5578.38、PMID  12098683。
• リード、BA (1986)、半強完全グラフ定理、博士論文、モントリオール、ケベック、カナダ：マギル大学コンピュータサイエンス学部。 Roussel、Rusu & Thuillier (2009) が引用したとおり。
• Roussel, F.; Rusu, I.; Thuillier, H. (2009)、「強いパーフェクトグラフ予想: 40 年間の試みとその解決」、離散数学、309 (20): 6092–6113、doi : 10.1016/j.disc.2009.05.024、MR  2552645。
• ルス、イレーナ (1997)、「反例の構築」、離散数学、171 (1–3): 213–227、doi :10.1016/S0012-365X(96)00081-7、MR  1454452。
• シーモア、ポール(2006)、「強完全グラフ予想の証明がどのように発見されたか」(PDF)、Gazette des Mathématiciens (109): 69–83、MR  2245898。

• 強力な完全グラフ定理、ヴァーツラフ フヴァータル
• Weisstein、Eric W.「強い完全グラフ定理」。MathWorld。