禁止グラフの特性

グラフ理論は数学の一分野であり、多くの重要なグラフ族は、その族に属さない個々のグラフの有限集合によって記述することができ、さらに、これらの禁止されたグラフのいずれかを（誘導）部分グラフまたはマイナーとして含むすべてのグラフをその族から除外することができます。

この現象の典型的な例はクラトフスキーの定理であり、グラフが平面グラフ（平面上に交差なく描画できるグラフ）であるのは、完全グラフK ₅と完全二部グラフK _3,3のいずれも含まない場合に限られると述べています。クラトフスキーの定理における包含の概念は、グラフ同相写像の概念であり、一方のグラフの分割が他方のグラフの部分グラフとして現れることを意味します。したがって、すべてのグラフは平面描画を持つか（その場合、平面グラフの族に属する）、または少なくともこれら 2 つのグラフの分割を部分グラフとして持つか（その場合、平面グラフには属さない）のいずれかになります。

より一般的に言えば、禁止グラフ特性とは、グラフまたはハイパーグラフ構造の族を指定する方法であり、その族内のどのグラフにも存在が禁止されている部分構造を指定することによって行われます。禁止されるものの性質は、族によって異なります。一般に、構造Gは族のメンバーです。$\displaystyle {\mathcal {F}}}$禁止部分構造がGに含まれていない場合に限る。禁止部分構造は以下のいずれかである可能性がある。

• 部分グラフとは、より大きなグラフの頂点と辺の部分集合から得られるより小さなグラフのことです。
• 誘導部分グラフ、頂点のサブセットを選択し、そのサブセットの両端点を持つすべてのエッジを使用することによって得られるより小さなグラフ、
• 同相部分グラフ（トポロジカルマイナーとも呼ばれる）、次数2の頂点のパスを単一のエッジに縮約することによって部分グラフから得られるより小さなグラフ、または
• グラフマイナーとは、部分グラフから任意のエッジ縮約によって得られるより小さなグラフのことです。

特定のグラフ族に属することが禁じられている構造の集合は、そのグラフ族に対する障害集合とも呼ばれる。

禁止グラフ特性は、グラフが特定のファミリーに属するかどうかを判定するアルゴリズムに利用できます。多くの場合、与えられたグラフが禁止集合のいずれかの要素を含んでいるかどうか、つまりその禁止集合によって定義されるファミリーに属するかどうかを多項式時間で判定することが可能です。

あるグラフ族が特定のタイプのサブストラクチャを持つ禁止グラフ特性を持つためには、そのグラフ族はサブストラクチャに関して閉じていなければなりません。つまり、そのグラフ族に含まれるグラフのすべてのサブストラクチャ（特定のタイプ）は、そのグラフ族に含まれる別のグラフでなければなりません。言い換えれば、あるグラフがグラフ族に含まれていない場合、そのグラフをサブストラクチャとして含むより大きなグラフもすべてグラフ族から除外されなければなりません。これが真である場合、常に障害集合（グラフ族には含まれないが、そのより小さなサブストラクチャがすべてグラフ族に属するグラフの集合）が存在します。しかし、サブストラクチャの定義によっては、この障害集合は無限になることがあります。ロバートソン・シーモアの定理は、グラフマイナーの特定の場合において、マイナーに関して閉じているグラフ族は常に有限の障害集合を持つことを証明しています。

• エルデシュ・ハイナル予想
• 禁止部分グラフ問題
• マトロイドマイナー
• ザランキエヴィッチ問題