メイニエルグラフ

グラフ理論において、メイニエルグラフは、長さが5以上の奇数サイクルごとに少なくとも2本の弦（サイクルの連続しない頂点を結ぶ辺）があるグラフである。 ^[1]弦は交差していなくてもよい（図を参照）し、少なくとも2本あれば交差してもよい。

メイニエルグラフは、1976年にそれが完全グラフであることを証明したアンリ・メイニエル（メイニエル予想でも知られる）にちなんで名付けられました。 ^{[2]それは、}強い完全グラフ定理の証明が完全グラフを完全に特徴付けるよりずっと前のことでした。同じ結果は、マルコジャンとカラペジャン（1976年）によって独立に発見されました。^[3]

メイニエルグラフはパーフェクトグラフのサブクラスである。メイニエルグラフの誘導部分グラフはすべて別のメイニエルグラフであり、すべてのメイニエルグラフにおいて最大クリークのサイズはグラフの彩色に必要な最小色数に等しい。したがって、メイニエルグラフは、クリーク数がすべての誘導部分グラフの彩色数に等しいというパーフェクトグラフの定義を満たしている。^{[1] [2] [3]}

メイニエルグラフは、非常に強完全グラフとも呼ばれます。これは、（メイニエルが予想し、ホアンが証明したように）強完全グラフの定義特性を一般化した特性によって特徴付けられるためです。つまり、メイニエルグラフのすべての誘導サブグラフにおいて、すべての頂点はすべての最大クリークと交差する独立集合に属します。^{[1] [4]}

メイニエルグラフには、弦グラフ、パリティグラフ、およびそれらのサブクラスである区間グラフ、距離遺伝グラフ、二部グラフ、およびラインパーフェクトグラフが含まれます。^[1]

メイニエル グラフは完全グラフの非常に一般的なサブクラスを形成しますが、すべての完全グラフが含まれているわけではありません。たとえば、ハウス グラフ (弦が 1 本だけの五角形) は完全ですが、メイニエル グラフではありません。

メイニエルグラフは多項式時間で認識することができ、^{[5] 、任意のグラフに対して}NP困難なグラフ着色を含むいくつかのグラフ最適化問題は、メイニエルグラフに対して多項式時間で解くことができる。^{[6] [7]}