完璧なグラフ

グラフ理論において、完全グラフとは、グラフ自体とすべての誘導サブグラフの両方において、彩色数が最大クリークのサイズに等しいグラフのことである。すべてのグラフにおいて、彩色数は最大クリークのサイズ以上であるが、大きく離れている場合もある。これらの数が等しく、任意の頂点のサブセットを削除した後も等しい場合、グラフは完全である。

パーフェクトグラフには多くの重要なグラフ族が含まれ、それらの族における彩色とクリークに関する結果を統一するのに役立つ。例えば、すべてのパーフェクトグラフにおいて、グラフ彩色問題、最大クリーク問題、最大独立集合問題はすべて、非パーフェクトグラフではより複雑であるにもかかわらず、多項式時間で解くことができる。さらに、部分順序集合に関するディルワースの定理とミルスキーの定理、マッチングに関するケーニッヒの定理、単調数列に関するエルデシュ・シェケレスの定理など、組合せ論におけるいくつかの重要なミニマックス定理は、特定の関連グラフの完全性によって表現できる。

パーフェクトグラフ定理は、パーフェクトグラフの補グラフもパーフェクトであることを述べています。強いパーフェクトグラフ定理は、特定の禁止誘導サブグラフの観点からパーフェクトグラフを特徴付け、グラフがパーフェクトかどうかをテストするための多項式時間アルゴリズムにつながります。

無向グラフのクリークは、その頂点がすべて互いに隣接している部分集合です。たとえば、図では太い辺で接続された頂点の部分集合がこれにあたります。クリーク数は、最大のクリークの頂点の数です。図の 7 頂点サイクルでは 2 頂点、他の図では 3 頂点です。グラフの色付けでは、各頂点に色を割り当てて、隣接する 2 つの頂点が異なる色になるようにします。これも図に示されています。グラフの彩色数は、任意の色付けにおける最小の色数です。図に示されている色付けは最適であるため、彩色数は 7 サイクルでは 3 で、他の図に示されているグラフでは 4 です。クリークの頂点はそれぞれ異なる色である必要があるため、彩色数は常にクリーク数以上になります。一部のグラフでは、彩色数は等しくなりますが、他のグラフ (図に示されているものなど) では、彩色数は等しくありません。完全グラフは、グラフ自体だけでなく、その頂点のいくつかを削除することによって得られるすべての誘導サブグラフにおいて、これら2つの数が等しいグラフとして定義されます。^[1]

パーフェクトグラフ定理は、パーフェクトグラフの補グラフはそれ自体がパーフェクトであることを主張する。補グラフが2つの頂点の間に辺を持つのは、与えられたグラフが辺を持たない場合のみである。補グラフ内のクリークは、与えられたグラフ内の独立集合に対応する。補グラフの色付けは、与えられたグラフの頂点をクリークに分割したクリーク被覆に対応する。パーフェクトグラフの補グラフもパーフェクトであるという事実は、それ自体で、独立数（その最大独立集合のサイズ）がクリーク被覆数（クリーク被覆に必要なクリークの最小数）に等しいことを意味する。より強く、同じことが補グラフのすべての誘導サブグラフにも当てはまる。これは、パーフェクトグラフの代替かつ同等の定義を提供する。パーフェクトグラフとは、各誘導サブグラフで独立数がクリーク被覆数に等しいグラフである。^{[2] [3]}${\displaystyle G}$${\displaystyle G}$

強いパーフェクトグラフ定理は、パーフェクトグラフをその特性ではなく構造によって定義する別の方法を提供します。これは、与えられたグラフ内のサイクルグラフとその補グラフの存在に基づいています。3 より大きい奇数長のサイクルは完全ではありません。そのクリーク数は 2 ですが、彩色数は 3 です。パーフェクトグラフ定理によれば、長さが 3 より大きい奇数サイクルの補グラフも完全ではありません。長さが 5 のサイクルの補グラフは別の長さが 5 のサイクルですが、より大きな奇数長の場合、補グラフはサイクルではなく、反サイクルと呼ばれます。強いパーフェクトグラフ定理は、これらがパーフェクトグラフの唯一の禁制の誘導サブグラフであると主張しています。グラフが完全であるためには、その誘導サブグラフに 5 つ以上の頂点の奇数サイクルも奇数反サイクルも含まれません。この文脈では、三角形ではない誘導サイクルは「ホール」と呼ばれ、その補数は「アンチホール」と呼ばれるため、強いパーフェクトグラフ定理はより簡潔に述べることができます。グラフがパーフェクトであるのは、奇数のホールも奇数のアンチホールも存在しない場合のみです。 ^[4]

これらの結果は、パーフェクト グラフの別の特徴付けに組み合わせることができます。パーフェクト グラフとは、クリーク数と独立数の積が頂点数以上であり、すべての誘導サブグラフについて同じことが当てはまるグラフです。この特徴付けの記述はグラフの補完の下で不変であるため、パーフェクト グラフ定理が暗示されます。この特徴付けの 1 つの方向性は、パーフェクトの元の定義から簡単に導き出されます。つまり、どのグラフでも、頂点数は最適な色分けにおける色クラスのサイズの合計に等しく、色の数に独立数を掛けた値以下です。パーフェクト グラフでは、色の数はクリーク数に等しく、この不等式ではクリーク数に置き換えることができます。他の方向は直接証明できるが^{[5] [6]}、これは強い完全グラフ定理からも導かれる。つまり、グラフが完全でない場合、奇数サイクルまたはその補数を含み、これらの部分グラフではクリーク数と独立数の積は頂点数より1少ない。^[7]

パーフェクトグラフの理論は、1958 年のティボール・ガライの結果から発展した。現代語で言えば、二部グラフの補グラフはパーフェクトであると述べていると解釈できる。^{[8]この結果は、二部グラフのマッチングと頂点被覆を関連付けるかなり以前の結果である}ケーニッヒの定理の単純な同等物と見ることもできる。パーフェクトグラフの概念がより一般的に初めて定式化されたのは、クロード・ベルゲによる 1961 年のドイツ語の論文であり、^[9]「パーフェクトグラフ」という語句が初めて使用されたのは、1963 年のベルゲの論文であると思われる。^[10]これらの研究で、ベルゲはパーフェクトグラフを定義することでガライの結果といくつかの同様の結果を統合し、パーフェクトグラフ定理と強いパーフェクトグラフ定理の両方を推測した。これらの概念を定式化するにあたり、ベルゲはグラフのシャノン容量の概念、（共）完全グラフの場合それが独立数に等しいという事実、そしてこれが当てはまらないグラフの最小の例の探索に動機づけられた。^[11]強い完全グラフ定理が証明されるまで、それによって記述されるグラフ（つまり、奇数ホールと奇数反ホールのないグラフ）はベルゲグラフと呼ばれていた。^[12]

完全グラフ定理は1972年にラースロー・ロヴァースによって証明されました。 ^[2]彼は同年、強い完全グラフ定理に頼ることなく、頂点の数とクリーク数と独立数の積との間のより強い不等式を証明しました。^[5] 1991年、アルフレッド・レーマンは、完全グラフ理論の論理行列への一般化に関する研究により、数学最適化学会とアメリカ数学会が共同で主催するフルカーソン賞を受賞しました。^[13]予想された強いパーフェクトグラフ定理は、パーフェクトグラフ理論の研究の焦点となって長年に渡って続き、^[12]その証明が2002年にマリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマスによって発表され、^[14] 2006年に出版された。 ^[4]この研究により、著者らは2009年のフルカーソン賞を受賞した。^[15]パーフェクトグラフ定理の証明は短いが^{[5] [6]}、強いパーフェクトグラフ定理の証明は長く専門的であり、ベルゲグラフの深い構造分解に基づいている。関連する分解技術は、他のグラフクラス、特にクローフリーグラフの研究でも成果を上げている。^[16]クリーク数と独立数の積によるパーフェクトグラフの対称的な特徴付けは、もともとハジナルによって提案され、ロヴァースによって証明された。^[5]

よく研究されているグラフの族の多くは完全であり、^[12]多くの場合、これらのグラフが完全であるという事実は、これらのグラフによって定義されるいくつかの種類の組合せ構造に対するミニマックス定理に対応しています。この現象の例には、最大マッチングと二部グラフの頂点被覆に関するケーニッヒの定理に関連する二部グラフとその線グラフの完全性、および半順序集合の鎖と反鎖に関するディルワースの定理とミルスキーの定理に関連する比較可能性グラフの完全性が含まれます。強い完全グラフ定理のホールと反ホールに関連する構造を持つことで定義される他の重要なグラフのクラスには、弦グラフ、メイニエルグラフ、およびそれらのサブクラスがあります。

二部グラフ（少なくとも 1 つの辺を持つ）では、彩色数とクリーク数はどちらも 2 に等しい。それらの誘導サブグラフは二部のままなので、二部グラフは完全である。 ^[12]他の重要なグラフ族も二部であり、したがって完全であり、これには木や中央値グラフが含まれる。^[17]完全グラフ定理により、二部グラフの最大独立集合は、最小クリーク被覆と同じサイズである。最大独立集合は、すべての辺に接する頂点の集合である最小頂点被覆と補完関係にある。最小クリーク被覆は、最大マッチング（可能な限り多くの互いに素な辺）と、残りのすべての頂点に対する 1 頂点クリークで構成され、そのサイズは頂点数からマッチング辺の数を引いた値である。したがって、この等式は、二部グラフにおける最大マッチングの大きさと最小頂点被覆との間の等式として等しく表現することができ、これはケーニッヒの定理の通常の定式化である。^{[18] [19]}

任意のグラフ におけるマッチングは、内の各辺に対して頂点を持ち、内の端点を共有する辺の各ペアに対して 内の 2 つの頂点間に辺を持つグラフである線グラフ内の独立集合と同じものである。線グラフには、共通の端点を持つ 内の辺の集合と 内の三角形の 2 種類のクリークがある。二部グラフには三角形がないので、 内のクリーク被覆は内の頂点被覆に対応する。したがって、二部グラフの線グラフでは、独立数とクリーク被覆数は等しい。二部グラフの線グラフの誘導部分グラフは部分グラフの線グラフなので、二部グラフの線グラフは完全である。^[19]例としては、ルークのグラフ、完全二部グラフの線グラフなどがある。二部グラフのすべての線グラフは、ルークのグラフの誘導部分グラフである。^[20]${\displaystyle G}$ ${\displaystyle L(G)}$${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle G}$

二部グラフの線グラフは完全であるため、クリーク数は彩色数に等しい。二部グラフの線グラフのクリーク数は、基礎となる二部グラフの任意の頂点の最大次数である。二部グラフの線グラフの彩色数は、基礎となる二部グラフの彩度指数であり、接触する辺が異なる色になるように辺を着色するために必要な最小の色数である。各色クラスはマッチングを形成し、彩度指数はすべての辺をカバーするために必要なマッチングの最小数である。二部グラフにおける最大次数と彩度指数の等式は、デーネス・ケーニヒの別の定理である。^[21]任意の単純グラフでは、それらは 1 つだけ異なることがある。これはヴィイジングの定理である。^[19]

完全線グラフの基礎となるグラフは、線完全グラフである。これらは、2部グラフ、完全グラフ、および三角形の本（辺を共有する三角形の集合）を2連結成分とするグラフである。これらの成分は完全であり、それらの組み合わせは完全性を保つため、すべての線完全グラフは完全である。^[19]${\displaystyle G}$${\displaystyle L(G)}$ ${\displaystyle K_{4}}$

二部グラフ、その補グラフ、二部グラフとその補グラフの線グラフは、4つの基本的な完全グラフのクラスを形成し、強い完全グラフ定理の証明において重要な役割を果たす。この証明の一部として使用される完全グラフの構造分解によれば、これら4つのクラスのいずれにも属さないすべての完全グラフは、2結合、2結合の補グラフ、同次対、または歪曲分割と呼ばれる4つの方法のいずれかで頂点を部分集合に分割することによって分解できる。 [ ^3]

半順序集合は、その要素の集合と、反射的（すべての要素、に対して）、反対称的（およびであれば）、推移的（および であれば）な比較関係によって定義されます。要素と は、またはの場合に比較可能であり、それ以外の場合は比較不可能です。たとえば、集合包含（）は、任意の集合族 を部分的に順序付けます。半順序集合の比較可能性グラフは、集合の要素を頂点とし、比較可能な任意の 2 つの要素を辺で接続します。その補集合は比較不可能グラフと呼ばれます。異なる半順序でも同じ比較可能グラフを持つ場合があります。たとえば、すべての比較を逆にすると、順序は変わりますがグラフは変わりません。^[22]${\displaystyle \leq }$${\displaystyle x}$${\displaystyle x\leq x}$${\displaystyle x\leq y}$${\displaystyle y\leq x}$${\displaystyle x=y}$${\displaystyle x\leq y}$${\displaystyle y\leq z}$${\displaystyle x\leq z}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\leq y}$${\displaystyle y\leq x}$${\displaystyle \subseteq }$

有限比較可能性グラフ（およびその相補的な非比較可能性グラフ）は常に完全である。^[23]比較可能性グラフ内のクリークは、すべて一対一で比較可能な要素のサブセットから生成されます。このようなサブセットはチェーンと呼ばれ、与えられた半順序によって線形に順序付けられます。独立集合は、2 つとして比較できない要素のサブセットから生成されます。このようなサブセットはアンチチェーンと呼ばれます。たとえば、図に示した半順序と比較可能性グラフでは、は順序内のチェーンでグラフ内のクリークであり、 は順序内のアンチチェーンでグラフ内の独立集合です。したがって、比較可能性グラフの色付けはその要素をアンチチェーンに分割することであり、クリーク カバーはその要素をチェーンに分割することです。半順序理論におけるディルワースの定理は、すべての有限半順序について、最大のアンチチェーンのサイズは、要素を分割できるチェーンの最小数に等しいと述べています。グラフの言語で言えば、これは次のように述べられる。すべての有限比較可能グラフは完全である。同様に、ミルスキーの定理は、すべての有限半順序について、最大チェーンのサイズは、要素を分割できる反チェーンの最小数に等しい、またはすべての有限比較不可能グラフは完全である、と述べている。これら 2 つの定理は完全グラフ定理を介して同等であるが、ミルスキーの定理はディルワースの定理よりも直接証明しやすい。各要素が最大となる最大チェーンのサイズでラベル付けされている場合、等しいラベルを持つ部分集合は反チェーンへの分割を形成し、反チェーンの数は全体の最大チェーンのサイズに等しい。^[24]すべての二部グラフは比較可能グラフである。したがって、ケーニッヒの定理は、完全グラフの理論を介して接続されたディルワースの定理の特別なケースと見なすことができます。^[25]${\displaystyle \{A,B,C\}}$${\displaystyle \{C,D\}}$

順列グラフは、グラフの頂点を形成する要素（慣例的には、から までの整数）の完全に順序付けられたシーケンス上の順列から定義されます。順列グラフの辺は、与えられた順列によって順序が逆になる要素のペアを接続します。これらは、与えられたシーケンスとその順列の両方でが前に現れる半順序に対して、当然比較不可能なグラフです。順列グラフの補グラフは、与えられた順列の逆に対する別の順列グラフです。したがって、順列グラフは比較不可能なグラフであると同時に、比較可能グラフでもあります。実際、順列グラフは、比較可能グラフとも比較不可能なグラフともいえるグラフです。^[26]順列グラフにおけるクリークは、与えられた順列で昇順に現れる要素の部分列であり、独立集合は降順に現れる要素の部分列です。任意の完全グラフにおいて、クリーク数と独立数の積は少なくとも頂点数である。順列グラフにおけるこの不等式の特殊なケースはエルデシュ・シェケレスの定理である。^[24]${\displaystyle 1}$${\displaystyle n}$${\displaystyle x\leq y}$${\displaystyle x}$${\displaystyle y}$

区間グラフは、区間順序の比較不可能グラフです。区間 が区間 の完全に左側にある場合は常に、 を伴う実数直線上の区間の集合によって順序が定義されます。対応する区間グラフでは、2 つの区間に共通点がある場合は常に、からへのエッジが存在します。これらのグラフの色付けは、各タスクの予定時間を表す区間を使用して、リソースをタスクに割り当てる問題 (教室をクラスに割り当てるなど) をモデル化するために使用できます。 ^{[27]区間グラフと順列グラフはどちらも、}台形グラフによって一般化されます。^[28] 2 つが入れ子になっていない区間のシステムは、より制限されたクラスのグラフ、無差別グラフ、半順序の比較不可能グラフを生成します。これらは、項目の効用が互いに非常に近い場合、それらは比較不可能であるという仮定の下で、人間の好みをモデル化するために使用されてきました。^[29]すべてのペアが入れ子になっているか互いに素である区間は、自明に完全なグラフ、^[30]順序付き木の比較可能性グラフを生成します。それらにおいて、独立数は最大クリークの数に等しくなります。^[31]${\displaystyle x\leq y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

分割グラフは、クリークと独立集合に分割できるグラフである。最大クリークの各頂点に別々の色を割り当て、残りの各頂点を隣接していないクリークの頂点と同じ色にすることで、分割グラフを色付けすることができる。したがって、これらのグラフはクリーク数と彩色が等しく、完全である。^[32]より広いグラフのクラスである単極グラフは、クリークと、クリークの非結合和であるクラスターグラフに分割することができる。これには、クラスターグラフが単一のクリークである二部グラフも含まれる。単極グラフとその補グラフは、一般化分割グラフのクラスを形成する。ほぼすべての完全グラフは、一般化分割グラフであるという意味であり、一般化分割グラフである完全 - 頂点グラフの割合は、が任意に大きくなるにつれて極限で 1 になる。^[33]${\displaystyle n}$${\displaystyle n}$

ほぼすべての完全グラフのその他の極限特性は、一般化分割グラフを調べることで決定できます。この方法で、ほぼすべての完全グラフにハミルトン閉路が含まれていることが示されています。が任意のグラフである場合、大きなランダム完全グラフの誘導サブグラフとして発生する極限確率は、一般化分割グラフではない場合、単極性または共単極性であるが両方ではない場合、または単極性と共単極性の両方である場合にそれぞれ0、1/2、1です。^[34]${\displaystyle H}$${\displaystyle H}$${\displaystyle H}$

完全グラフのいくつかの族は、一定の規則に従って一度に 1 つの頂点を追加することによって族内のグラフが構築される増分構築によって特徴付けられ、各頂点が追加された後もグラフが完全のままであることが保証されます。

• 弦グラフとは、頂点が追加される時点でその近傍がクリークを形成するような構成によって形成されるグラフである。弦グラフは、穴（偶数または奇数）のないグラフとしても特徴付けられる。^[35]特殊なケースとして、フォレスト、区間グラフ、^[36]および最大外平面グラフが含まれる。^[37]分割グラフは、弦グラフであり、弦補集合を持つグラフである。^[38]木幅の定義の中心となるk木は、 ( k + 1)頂点クリークから始めて、その近傍とその近傍が同じサイズのクリークを形成するように頂点を繰り返し追加することによって形成される弦グラフである。^[35]

• 距離遺伝グラフは、単一頂点グラフから始まり、次数 1 の頂点 (「ペンダント頂点」) または既存の頂点のコピー (同じ隣接頂点を持つ) を繰り返し追加することによって形成されます。各頂点とそのコピーは隣接している場合 (真の双子) と隣接していない場合があります (偽の双子)。これらのグラフのすべての接続された誘導サブグラフでは、頂点間の距離はグラフ全体と同じです。双子操作のみが使用される場合、結果はコグラフになります。^{[39]コグラフは、}直列並列部分順序の比較可能性グラフであり^{[40] 、}グラフの補完と非結合和集合を組み合わせた別の構築プロセスによっても形成されます。^[41]
• 弦グラフかつ距離遺伝グラフは、その距離がプトレマイオスの不等式に従うため、プトレマイオスグラフと呼ばれます。^[42]これらは距離遺伝構築シーケンスの制限された形式を持ち、偽の双子は、その隣接がクリークを形成する場合にのみ追加できます。^{[39]特殊なケースとして、単一の頂点で結合されたクリークで構成される}風車グラフと、各2連結コンポーネントがクリークであるブロックグラフが含まれます。 ^[42]
• 閾値グラフは、孤立した頂点（他に何も接続されていない）または普遍的な頂点（他のすべての頂点に接続されている）のいずれかを繰り返し追加することによって空のグラフから形成されます。 ^[43]これらは、分割グラフと自明に完全グラフの特別なケースです。これらは、自明に完全であり、自明に完全グラフの補グラフであるグラフです。また、コグラフと分割グラフの両方であるグラフでもあります。^[44]

弦グラフの頂点を、貪欲彩色アルゴリズムを使用して増分構築シーケンスの順序で彩色すると、最適な彩色が得られます。この構築で使用される頂点順序の逆は、消去順序と呼ばれます。^[45]同様に、距離遺伝グラフの頂点を増分構築シーケンスの順序で彩色すると、結果の彩色は最適になります。^{[46]比較可能性グラフの頂点を、その基礎となる部分順序の}線形拡張の順序で彩色すると、結果の彩色は最適になります。 この特性は、完全に順序付け可能なグラフの族、つまり、任意の誘導サブグラフに制限された場合に貪欲彩色が最適になるような順序付けが存在するグラフに一般化されています。^[47]コグラフは、すべての頂点順序付けがこの特性を持つグラフです。^[48]完全に順序付け可能なグラフのもう一つのサブクラスは、区間グラフの一般化である許容グラフの補グラフである。 ^[49]

強く完全グラフとは、すべての誘導部分グラフにおいて、すべての極大クリークと交差する独立集合が存在するグラフである。メイニエルグラフまたは非常に強く完全グラフでは、すべての頂点がそのような独立集合に属する。メイニエルグラフは、長さ5以上のすべての奇数サイクルに少なくとも2つの弦があるグラフとしても特徴付けられる。^[50]

パリティ グラフは、 2 つの頂点間のすべての誘導パスが等しいパリティを持つという特性によって定義されます。つまり、すべての誘導パスの長さが偶数か、すべての誘導パスの長さが奇数です。これには、2 つの頂点間のすべての誘導パスが同じ長さを持つ距離遺伝グラフ^[51]と、任意の 2 つの頂点間のすべてのパス (誘導パスだけではない) が等しいパリティを持つ 2 部グラフが含まれます。パリティ グラフはメイニエル グラフであるため、完全です。長い奇数サイクルに 1 つの弦しかない場合、弦の端点間のサイクルの 2 つの部分は、異なるパリティの誘導パスになります。任意のパリティ グラフ上のプリズム ( 1 つの辺との直積) は別のパリティ グラフであり、パリティ グラフはプリズムが完全である唯一のグラフです。^[52]

パーフェクトグラフは、線形計画法および整数計画法の理論と密接に関係しています。線形計画法と整数計画法はどちらも、線形制約およびを条件として、線形目的関数を最大化するベクトルを求める標準形式で表現されます。ここで、は行列として与えられ、および は2 つのベクトルとして与えられます。線形計画法と整数計画法は同じように指定されますが、線形計画法では解ベクトルの係数として任意の実数を持つことができるのに対し、整数計画法ではこれらの未知の係数は整数でなければならないという点で異なります。これは、これらの問題の計算の複雑さに大きな違いをもたらします。線形計画法は多項式時間で解くことができますが、整数計画法はNP 困難です。^[1] ${\displaystyle x}$ ${\displaystyle c\cdot x}$${\displaystyle x\geq 0}$${\displaystyle Ax\leq b}$${\displaystyle A}$${\displaystyle b}$${\displaystyle c}$${\displaystyle x}$

同じ与えられた値、、 が線形計画と整数計画の両方を定義するために使用された場合、通常、それらの最適解は異なります。整数計画の最適解が線形計画にとっても最適である場合、線形計画は積分線形計画と呼ばれます。（そうでない場合、2つの解の値の比は積分ギャップと呼ばれ、整数計画の近似アルゴリズムを解析する際に重要です。）完全グラフは、次の特性を持つ(0, 1) 行列（つまり、すべての係数が 0 または 1 である行列）を特徴付けるために使用できます。 がすべて 1 のベクトルの場合、結果として得られる線形計画のすべての選択に対して、は積分です。^[1]${\displaystyle A}$${\displaystyle b}$${\displaystyle c}$ ${\displaystyle A}$${\displaystyle b}$${\displaystyle c}$

ヴァーツラフ・クヴァータルが証明したように、この特性を持つすべての行列は（無関係な「支配」行を除けば）完全グラフの最大クリーク対頂点接続行列である。この行列はグラフの各頂点に対して1列、各最大クリークに対して1行を持ち、クリークに属する頂点の列の係数は1、残りの列の係数は0である。この行列で符号化された積分線形計画法は、ベクトル によって重みが与えられる、与えられたグラフの最大重み独立集合を求める。^{[1] [53]}${\displaystyle A}$${\displaystyle c}$

完全グラフからこのように定義された行列に対して、不等式系を満たすベクトルは積分多面体を形成する。これはグラフ内の独立集合の指示ベクトルの凸包であり、面はグラフ内の最大クリークに対応する。完全グラフは、独立集合と最大クリークからこのように定義された2つの多面体が一致する唯一のグラフである。^[53]${\displaystyle A}$${\displaystyle x}$${\displaystyle x\geq 0}$${\displaystyle Ax\leq 1}$

すべての完全グラフでは、グラフ彩色問題、最大クリーク問題、最大独立集合問題はすべて多項式時間で解くことができます。一般的な場合のアルゴリズムには、これらのグラフのLovász 数が含まれます。任意のグラフの Lovász 数は、2 つの隣接しない頂点のラベルがそれぞれ垂直になるように、またすべてのベクトルが可能な限り小さな開口角を持つ円錐内に位置するように、その頂点に高次元の単位ベクトル でラベルを付けることで決定できます。この場合、Lovász 数は で、 はこの円錐の半角です。この複雑な定義にもかかわらず、Lovász 数の正確な数値は半正定値計画法を使用して計算でき、任意のグラフに対して Lovász 数は彩色数とクリーク数の間にあります。これら 2 つの数は完全グラフでは互いに等しいため、Lovász 数にも等しくなります。したがって、ロヴァース数を十分に正確に近似し、結果を最も近い整数に丸めることで計算することができます。^{[54] [55]}${\displaystyle 1/\cos ^{2}\theta }$${\displaystyle \theta }$

このアルゴリズムで使用される半正定値計画法の解法は、線形計画法の楕円体法に基づいています。これは、完全グラフの彩色数とクリーク数を計算する多項式時間アルゴリズムにつながります。しかし、ロヴァース数と楕円体法を使用してこれらの問題を解くことは複雑であり、多項式指数が高くなります。^{[54] [55]}多くの特殊なケースでは、より効率的な組み合わせアルゴリズムが知られています。^[56]

この方法は、重み付きグラフのクリーク番号の代わりに、クリークの最大重みを見つけるために一般化することもできます。最大または最大重みクリーク自体、およびグラフの最適な色付けもこれらの方法で見つけることができ、同じアプローチをグラフの補集合に適用することで最大独立集合を見つけることができます。たとえば、最大クリークは次のアルゴリズムで見つけることができます。^[54]

• グラフの頂点をループします。各頂点に対して、次の手順を実行します。 ${\displaystyle v}$
  • グラフから暫定的に削除します。${\displaystyle v}$
  • 半正定値計画法を使用して、結果として得られる誘導サブグラフのクリーク数を決定します。
  • このクリーク番号がグラフ全体のものと同じ場合は、 を永久に削除します。それ以外の場合は、グラフに復元します。${\displaystyle v}$${\displaystyle v}$
• すべての永久削除後に残っているサブグラフを返します。

最適な色付けを見つけるアルゴリズムはより複雑で、このクリーク検索アルゴリズムを分離オラクルとして使用して、線形計画の双対性理論に依存しています。^[54]

これらの問題を解決すること以外に、パーフェクトグラフに関するもう 1 つの重要な計算問題は、その認識、つまり与えられたグラフがパーフェクトかどうかをテストする問題です。長年、ベルジュグラフとパーフェクトグラフを認識する複雑さは別々に​​考えられてきました (まだ同等であることが知られていなかったため)。どちらも未解決のままでした。どちらもco-NPであることが知られていました。ベルジュグラフの場合、これは定義からわかります。^[57]一方、パーフェクトグラフの場合、これはクリーク数と独立数の積を使用した特徴付けからわかります。^[6]強いパーフェクトグラフ定理が証明された後、Chudnovsky、Cornuéjols、Liu、Seymour、および Vušković は、奇数ホールまたは反ホールの存在をテストするための多項式時間アルゴリズムを発見しました。強いパーフェクトグラフ定理により、これは与えられたグラフがパーフェクトかどうかを多項式時間でテストするために使用できます。^[58]

パーフェクトグラフを一般化すると、グラフクラスは、そのクラス内のグラフの彩色数がそのクリーク数の関数で制限される場合、χ-有界であると言われる。パーフェクトグラフとは、この関数がグラフ自体とそのすべての誘導サブグラフの両方に対して恒等関数となるグラフである。^[59]

パーフェクトグラフにおけるクリーク数と彩色数の等しさは、他のグラフ不変量が互いに等しく設定される他のグラフクラスの定義の動機となった。例えば、支配パーフェクトグラフは、すべての誘導サブグラフにおいて、最小の支配集合（残りのすべての頂点に隣接する頂点の集合）が、支配集合である最小の独立集合のサイズに等しいグラフとして定義される。これには、例えばクローフリーグラフが含まれる。^[60]

• Václav Chvátalによる強い完全グラフ定理。
• アメリカ数学協会によって管理されている、完全グラフに関する未解決問題。
• 完璧な問題、Václav Chvátal によって管理されています。
• グラフクラス包含に関する情報システム: 完全グラフ