自明に完璧なグラフ

グラフ理論において、自明完全グラフとは、その誘導されたサブグラフのそれぞれにおいて、最大独立集合の大きさが最大クリークの数に等しいという特性を持つグラフである。^[1]自明完全グラフは、(Wolk 1962, 1965) によって最初に研究されたが、Golumbic (1978) によって命名された。Golumbic は、「そのようなグラフが完全であることを示すのは自明であるため、この名前が選ばれた」と書いている。自明完全グラフは、木の比較可能性グラフ、^[2] 樹状比較可能性グラフ、^[3]および準閾値グラフとしても知られている。^[4]

自明に完全なグラフには、他にも同等の特徴がいくつかあります。

• これらは順序論的木の比較可能性グラフである。つまり、T を半順序とし、各t ∈ Tに対して集合{ s ∈ T  : s < t } が関係<によって整列しており、またT が最小元r を持つとする。するとTの比較可能性グラフは自明に完全であり、あらゆる自明に完全なグラフはこの方法で形成できる。^[5]
• これらは、 P ₄ パスグラフやC ₄ サイクルグラフを誘導部分グラフとして持たないグラフである。^[6]
• これらは、連結された誘導部分グラフの全てが普遍頂点を含むグラフである。^[7]
• これらは、ネストされた区間の集合に対する区間グラフとして表現できるグラフです。区間の集合がネストされているとは、集合内の2つの区間ごとに、2つが互いに素であるか、一方が他方を包含している場合です。^[8]
• これらは、弦グラフとコグラフの両方である。^[9]これは、弦グラフが長さが3を超える誘導サイクルを持たないグラフであり、コグラフが4つの頂点に誘導パスを持たないグラフであるという特徴付けから導か_れる（ P4 ）。
• これらはコグラフと区間グラフの両方であるグラフである。^[9]
• これらは、1頂点グラフから始めて、2つの操作、すなわち2つの小さな自明に完全なグラフの非結合和と、より小さな自明に完全なグラフのすべての頂点に隣接する新しい頂点の追加によって形成できるグラフです。^[10]これらの操作は、基礎となるフォレストでは、2つの小さなフォレストの非結合和によって新しいフォレストを形成し、フォレスト内のすべてのツリーのルートに新しいルートノードを接続してツリーを形成することに対応します。
• これらは、すべての辺uvに対して、uとvの近傍（uとv自身を含む）がネストされているグラフである。つまり、1つの近傍は他の近傍のサブセットでなければならない。^[11]
• これらはスタックソート可能な順列から定義された順列グラフである。^[12]
• これらは、各誘導サブグラフにおいてクリーク被覆数が最大クリークの数に等しいという性質を持つグラフである。^[13]
• これらは、その誘導された部分グラフの各々においてクリーク数が擬似グランディ数に等しいという性質を持つグラフである。 ^[13]
• これらは、その誘導された部分グラフの各々において彩色数が擬似グランディ数に等しいという性質を持つグラフである。 ^[13]

自明に完全グラフの同等の特徴付けから、すべての自明に完全グラフは、コグラフ、弦グラフ、プトレマイオスグラフ、区間グラフ、および完全グラフでもあることがわかります。

閾値グラフとは、それ自体が自明に完全であり、かつ自明に完全なグラフの補グラフ（共自明に完全なグラフ）であるグラフである。^[14]

風車グラフは自明に完璧です。

Chu (2008) は、辞書式幅優先探索に基づいて、自明に完璧なグラフを認識するための単純な線形時間アルゴリズムを説明しています。LexBFS アルゴリズムは、キューの最初のセットから頂点v を削除するたびに、 vの残りのすべての隣接頂点が同じセットに属しているかどうかを確認します。そうでない場合は、禁止された誘導サブグラフの 1 つをvから構築できます。このチェックがすべてのvに対して成功した場合、グラフは自明に完璧です。このアルゴリズムは、グラフが自明に完璧なグラフの補グラフであるかどうかを線形時間でテストするように変更することもできます。

一般的なグラフが自明に完全なグラフからk辺削除離れているかどうかを判断することはNP完全^[15]であり、固定パラメータで扱いやすく^{[16] 、} O (2.45k ⁽ m + n ) )時間で解くことができます。^[17]

• 「自明に完璧なグラフ」、グラフクラスとその包含に関する情報システム