完全グラフ定理

グラフ理論において、László Lovász  (1972a, 1972b)のパーフェクトグラフ定理は、無向グラフがパーフェクトであるためには、その補グラフもパーフェクトでなければならないと述べています。この結果はBerge (1961, 1963)によって推測されており、パーフェクトグラフをその禁制誘導部分グラフによって特徴付ける強いパーフェクトグラフ定理^[1] と区別するために、弱いパーフェクトグラフ定理と呼ばれることもあります。

完全グラフは、その誘導されたサブグラフのすべてにおいて、最大クリークのサイズがサブグラフの色付けにおける最小の色数に等しいという特性を持つ無向グラフです。完全グラフには、二部グラフ、弦グラフ、比較可能性グラフなど、多くの重要なグラフ クラスが含まれます。

グラフの補グラフが 2 つの頂点間に辺を持つのは、元のグラフが同じ 2 つの頂点間に辺を持たない場合のみです。したがって、元のグラフのクリークは補グラフの独立集合になり、元のグラフの色付けは補グラフの クリーク被覆になります。

完全グラフ定理は次のように述べます。

完全グラフの補グラフは完全です。

同様に、完全なグラフでは、最大独立集合のサイズは、クリークカバー内のクリークの最小数に等しくなります。

G を3 より大きい奇数の長さのサイクル グラフ(いわゆる「奇数ホール」) とします。この場合、Gはどの色付けでも少なくとも 3 色を必要としますが、三角形がないため完全ではありません。完全グラフ定理により、Gの補グラフ(「奇数反ホール」) も完全ではありません。G が 5 つの頂点のサイクルである場合、その補グラフ と同型ですが、この特性はより長い奇数サイクルには当てはまらず、奇数反ホールのクリーク数と彩色数を計算するのは奇数ホールの場合ほど簡単ではありません。強い完全グラフ定理が述べているように、奇数ホールと奇数反ホールは完全グラフの 最小の禁止誘導サブグラフであることがわかります。

非自明な二部グラフでは、最適な色の数は（定義により）2であり、（二部グラフには三角形がないので）最大クリークサイズも2である。また、二部グラフの誘導サブグラフはいずれも二部のままである。したがって、二部グラフは完全である。n頂点二部グラフでは、最小クリーク被覆は、最大マッチングと、マッチングされていない頂点ごとに追加のクリークを組み合わせた形をとり、サイズはn  −  Mである（ Mはマッチングの基数）。したがって、この場合、完全グラフ定理は、二部グラフの最大独立集合のサイズもn  −  Mであるというケーニッヒの定理を意味し、^[2]この結果は、ベルゲによる完全グラフ理論の定式化に大きな影響を与えた。

ミルスキーの定理は、半順序集合の高さを反鎖への分割によって特徴づけ、半順序集合の比較可能性グラフの完全性として定式化することができ、ディルワースの定理は、半順序集合の幅を鎖への分割によって特徴づけ、これらのグラフの補集合の完全性として定式化することができる。したがって、完全グラフ定理は、ミルスキーの定理の（はるかに簡単な）証明からディルワースの定理を証明するために使用することができ、その逆も同様である。^[3]

パーフェクトグラフ定理を証明するために、ロヴァースはグラフ内の頂点をクリークに置き換える操作を使用しました。グラフがパーフェクトであれば、この置き換え処理によって形成されるグラフもパーフェクトであることは、すでにベルゲに知られていました。^[4]このような置き換え処理は、頂点を2倍にする繰り返しステップに分解できます。2倍になった頂点がグラフの最大クリークに属する場合、クリーク数と彩色数が両方とも1増加します。一方、2倍になった頂点が最大クリークに属していない場合は、与えられたグラフの最適彩色から、2倍になった頂点と同じ色の頂点（2倍になった頂点自体は除く）を削除してグラフHを形成します。削除された頂点はすべての最大クリークと出会うため、H のクリーク数と彩色数は与えられたグラフよりも1少なくなります。削除された頂点と、2倍になった頂点の新しいコピーは、単一の色クラスとして追加することができ、この場合、2倍化のステップで彩色数は変化しないことがわかります。同じ議論から、2倍化によって、与えられたグラフのすべての誘導サブグラフでクリーク数と彩色数の等式が維持されるため、各2倍化ステップでグラフの完全性が維持されることが示されます。^[5]

完全なグラフGが与えられると、ロヴァースは各頂点v をt _v個の頂点のクリークで置き換えることによってグラフG *を形成します。ここでt _vはv を含むG内の異なる最大独立集合の数です。G 内の異なる最大独立集合のそれぞれを、 G *内の最大独立集合の 1 つと対応させることは可能です。その際、 G * 内の選択された最大独立集合はすべて互いに素であり、 G *の各頂点は単一の選択された集合に現れます。つまり、G * は、各色クラスが最大独立集合であるような彩色を持ちます。必然的に、この彩色はG * の最適彩色です。Gは完全であるため、G * も完全であり、したがって最大クリークK * を持ちます。このクリーク K * のサイズは、この彩色の色数、つまりG内の異なる最大独立集合の数に等しくなります。必然的に、K * にはこれらの最大独立集合のそれぞれに対する異なる代表が含まれます。Gの対応する頂点集合K ( G *の拡張クリークがK * と交差する頂点) は、Gのすべての最大独立集合と交差するという性質を持つGのクリークである。したがって、K を除去してGから形成されるグラフのクリーク被覆数はGのクリーク数より最大で 1 少なく、独立数はGの独立数より少なくとも 1 少なく、この数は帰納法で導かれる。 ^[6]

Chudnovsky ら (2006) の強い完全グラフ定理は、グラフが完全であるためには、その誘導されたサブグラフのいずれも 5 以上の奇数の長さのサイクルまたはその補数ではないと述べている。この特徴付けはグラフの補数の影響を受けないため、すぐに弱い完全グラフ定理が導かれる。

Cameron、Edmonds、Lovász (1986) は、完全グラフの辺が3 つのサブグラフに分割され、3 つの頂点ごとに 3 つのサブグラフのいずれかに接続されたグラフが誘導され、サブグラフのうち 2 つが完全であれば、3 番目のサブグラフも完全であることを証明しました。完全グラフ定理は、3 つのサブグラフのうち 1 つが空グラフである場合のこの結果の特殊なケースです。

• Berge、Claude (1961)、「Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind」、マルティン・ルター大学ハレ・ヴィッテンベルクのWissenschaftliche Zeitschrift der、Mathematisch-naturwissenschaftliche Reihe (ドイツ語)、10 : 114。
• ベルジュ、クロード(1963)、「完全グラフ」、グラフ理論に関する 6 つの論文、カルカッタ: インド統計研究所、pp. 1–21。
• キャメロン、K。エドモンズ、J . Lovász, L. (1986)、「完全なグラフに関するメモ」、Periodica Mathematica Hungarica、17 (3): 173–175、doi :10.1007/BF01848646、MR  0859346、S2CID  121018903。
• チュドノフスキー、マリア;ロバートソン、ニール;シーモア、ポール;トーマス、ロビン(2006)、「強い完全グラフ定理」、Annals of Mathematics、164 (1): 51–229、arXiv : math/0212070、doi :10.4007/annals.2006.164.51、MR  2233847、S2CID  119151552。
• マリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマス( 2003 )、「完全グラフの進歩」(PDF)、数理計画、シリーズ B、97 (1–2): 405–422、doi : 10.1007/s10107-003-0449-8、MR  2004404。
• Galrai、Tibor (1958)、「最大最小の Sätze über Graphen」、Acta Mathematica Academiae Scientiarum Hungaricae (ドイツ語)、9 (3–4): 395–434、doi :10.1007/BF02020271、MR  0124238
• ゴルビック、マーティン・チャールズ（1980）、「3.2. 完全グラフ定理」、アルゴリズムグラフ理論と完全グラフ、ニューヨーク：アカデミックプレス、pp. 53-58、ISBN 0-12-289260-7、MR  0562306。
• ケーニッヒ、デーネス(1931)、「Gráfok és mátrixok」、Matematikai és Fizikai Lapok (ハンガリー語)、38 : 116–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。
• リード、ブルース A. (2001)、「予想から定理へ」、ラミレス アルフォンシン、ホルヘ L.、リード、ブルース A. (編)、パーフェクト グラフ、Wiley-Interscience シリーズ、離散数学と最適化、チチェスター: Wiley、pp. 13–24、MR  1861356。