Loading article…
グラフ理論において、強完全グラフ定理は、完全グラフを奇数ホール（長さが5以上の奇数長誘導サイクル）も奇数アンチホール（奇数ホールの補集合）も持たないグラフとして定義する禁止グラフ特性である。これは1961年にクロード・ベルジュによって予想された。マリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマスによる証明が2002年に発表され[ 1 ]、2006年に彼らによって出版された。
強力完全グラフ定理の証明は、カーネギーメロン大学のジェラール・コルヌジョル氏から1万ドルの賞金[ 2 ]と2009年のフルカーソン賞[ 3 ]を獲得した。
完全グラフとは、すべての誘導部分グラフにおいて、最大クリークのサイズがグラフの彩色における最小色数に等しいグラフのことです。完全グラフには、二部グラフ、弦グラフ、比較グラフなど、よく知られた多くのグラフクラスが含まれます。クロード・ベルジュは、このグラフクラスを初めて定義した1961年と1963年の著作の中で、完全グラフには奇数ホール（長さが5以上の奇数長サイクルグラフの形をした誘導部分グラフ）は存在し得ないことを指摘しました。奇数ホールはクリーク数が2、彩色数が3であるためです。同様に、ベルジュは完全グラフには奇数アンチホール（奇数ホールの補完的な誘導部分グラフ）は存在し得ないことも指摘しました。2k + 1個の頂点を持つ奇数アンチホールは クリーク数がk、彩色数がk + 1であり、これも完全グラフではあり得ないことです。奇数ホールも奇数アンチホールも持たないグラフは、ベルジュグラフとして知られるようになりました。
ベルジュは、すべてのベルジュグラフは完全グラフである、あるいは同等に、完全グラフとベルジュグラフは同じグラフのクラスを定義すると予想した。これは、2002年に証明されるまで「強い完全グラフ予想」として知られていたが、証明された後に「強い完全グラフ定理」と改名された。
ベルジュのもう一つの予想は、1972年にラースロー・ロヴァースによって証明された、すべての完全グラフの補グラフもまた完全グラフであるというものである。これは完全グラフ定理、あるいは（強い完全グラフ予想／定理と区別するために）弱い完全グラフ定理として知られるようになった。ベルジュの禁止グラフ特性は自己補グラフであるため、弱い完全グラフ定理は強い完全グラフ定理から直ちに導かれる。
Chudnovsky らによる強完全グラフ定理の証明は、2001 年に Conforti、Cornuéjols、Robertson、Seymour、および Thomas によって予想された概要に従っており、それによると、すべての Berge グラフは、5 種類の基本構成要素 (完全グラフの特別なクラス) のいずれかを形成するか、より単純なグラフへの 4 種類の構造的分解のいずれかを持つ。最小限不完全な Berge グラフはこれらの分解のいずれも持つことができないため、この定理に対する反例は存在しないことになる。 [ 4 ]このアイデアは、強完全グラフ予想を導くはずだったが、実際には誤りであることが判明した、同様のタイプの構造的分解に関する以前の予想に基づいていた。[ 5 ]
この構造分解の基本ケースを構成する完全グラフの 5 つの基本クラスは、二部グラフ、二部グラフの線グラフ、二部グラフの補グラフ、二部グラフの線グラフの補グラフ、および二重分割グラフです。二部グラフが完全であることは容易にわかります。任意の非自明な誘導部分グラフでは、クリーク数と彩色数は両方とも 2 であり、したがって等しくなります。二部グラフの補グラフと二部グラフの線グラフの補グラフの完全性は、二部グラフにおける最大マッチング、最大独立集合、および最小頂点被覆のサイズを関連付けるKőnig の定理と同等です。二部グラフの線グラフの完全性は、二部グラフの彩色指数が最大次数に等しいという事実と同等に述べることができ、これはKőnig (1916)によって証明されています。したがって、これら 4 つの基本クラスはすべて完全です。二重分割グラフは分割グラフの親戚であり、完全であることが示されることもある。[ 6 ]
この証明で検討される4種類の分解は、2結合、2結合の補集合、バランスのとれた歪んだ分割、および同質ペアである。
2-ジョインとは、グラフの頂点を2つの部分集合に分割したもので、これらの2つの部分集合間のカットをまたぐ辺が、頂点が互いに素な2つの完全二部グラフを形成するという性質を持つ。グラフが2-ジョインを持つ場合、2つの部分集合のうちの1つを、2つの完全二部グラフのうちの1つをもう1つに接続する最短経路で置き換えることにより、「ブロック」と呼ばれる誘導部分グラフに分解できる。そのような経路が存在しない場合は、2つの部分集合のうちの1つを、各完全二部グラフに対応する2つの頂点で置き換えることにより、ブロックが形成される。2-ジョインは、その2つのブロックが両方とも完全である場合に限り、完全である。したがって、最小不完全グラフが2-ジョインを持つ場合、それはそのブロックの1つと等しくなければならず、そこから、そのグラフは奇数サイクルであり、ベルジュグラフではないことがわかる。同じ理由で、補グラフに2-結合を持つ最小不完全グラフはベルジュグラフにはなり得ない。[ 7 ]
スキュー分割とは、グラフの頂点を2つの部分集合に分割したもので、一方の部分集合は非連結部分グラフを誘導し、もう一方の部分集合は非連結補グラフを持つ。Chvátal (1985) は、強完全グラフ予想の最小反例はスキュー分割を持つことはできないと予想していた。Chudnovsky らはスキュー分割に関するいくつかの技術的な制約を導入し、結果として得られる「バランスのとれたスキュー分割」については Chvátal の予想が正しいことを示すことができた。完全な予想は強完全グラフ定理の系である。[ 8 ]
同質ペアは、グラフのモジュラー分解に関連しています。これは、グラフを 3 つの部分集合V 1、V 2、およびV 3に分割したもので、 V 1とV 2を合わせると少なくとも 3 つの頂点が含まれ、V 3には 少なくとも 2 つの頂点が含まれ、V 3の各頂点vと{1,2} の各iに対して、 vはV iのすべての頂点に隣接しているか、またはそれらのいずれにも隣接していません。最小限不完全なグラフでは同質ペアを持つことはできません。[ 9 ]強力な完全グラフ予想の証明の後、Chudnovsky (2006)は、証明で使用される分解の集合から同質ペアを削除できることを示すことで、それを簡略化しました。
すべてのベルゲグラフが 5 つの基本クラスのいずれかに属するか、4 つのタイプの分解のいずれかを持つことの証明は、グラフ内に特定の構成が存在するかどうかに応じてケース分析によって行われます。その構成とは、特定の追加制約に従って 3 つの誘導パスに分解できる部分グラフである「ストレッチャー」、ストレッチャーの補グラフ、および誘導サイクルと少なくとも 3 つのサイクル頂点に隣接するハブ頂点から構成され、いくつかの追加制約に従うホイールグラフに関連する構成である「適切なホイール」です。与えられたベルゲグラフ内にストレッチャー、その補グラフ、または適切なホイールが存在するかどうかの可能な選択ごとに、グラフが基本クラスのいずれかに属するか、分解可能であることが示されます。[ 10 ]このケース分析によって証明が完了します。