二部グラフは、各集合内のどの頂点も同じ集合内のどの頂点とも隣接しないように頂点を 2 つの集合に分割することができ、部分グラフとして奇数サイクルグラフを持たないという禁制の特性によって正確に記述されます。

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

この現象の典型的な例はクラトフスキーの定理で、グラフが平面的（平面上で交差することなく描画できる）であるためには、完全グラフ K 5と完全二部グラフ K 3,3という 2 つの禁制グラフのどちらも含まれないことを述べています。クラトフスキーの定理では、包含の概念はグラフ同相の概念であり、一方のグラフの分割がもう一方のグラフのサブグラフとして現れるものです。したがって、すべてのグラフは平面描画を持つか（その場合、平面グラフの族に属します）、または少なくとも 1 つのグラフをサブグラフとして細分化します（その場合、平面グラフには属しません）。

意味

より一般的には、禁制グラフの特徴付けとは、グラフ構造の族、またはハイパーグラフ構造を、族内のどのグラフにも存在が禁じられている部分構造を指定することによって特定する方法である。族によって禁制の性質は異なる。一般に、構造Gが族のメンバーとなるのは、禁制部分構造がGに含まれない場合のみである。禁制部分構造は、以下のいずれかである。

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

特定のグラフ ファミリに属する​​ことが禁止されている構造の集合は、そのファミリの 障害集合とも呼ばれます。

禁制グラフの特徴付けは、グラフが特定の族に属するかどうかをテストするアルゴリズムで用いられることがある。多くの場合、与えられたグラフが禁制集合のいずれかの要素を含むかどうか、つまりその禁制集合によって定義された族に属するかどうかを 多項式時間でテストすることができる。

族が特定の種類の部分構造を伴う禁制グラフ特徴付けを持つためには、族は部分構造に関して閉じている必要がある。つまり、族内のグラフのすべての部分構造（特定の種類）は、族内の別のグラフでなければならない。同様に、グラフが族の一部でない場合、それを部分構造として含むすべてのより大きなグラフも族から除外されなければならない。これが真である場合、常に障害集合（族には属さないが、より小さな部分構造がすべて族に属するグラフの集合）が存在している。しかし、部分構造の概念によっては、この障害集合が無限になることもある。ロバートソン・シーモアの定理は、グラフマイナーの特定のケースでは、マイナーに関して閉じている族は常に有限の障害集合を持つことを証明している。

グラフとハイパーグラフの禁止された特徴付けのリスト

参照

参考文献

  1. ^ abc Diestel, Reinhard (2000),グラフ理論, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, ISBN 0-387-98976-5。
  2. ^ Gupta, A.; Impagliazzo, R. (1991)、「Computing planar intertwines」、Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91)、IEEE Computer Society、pp.  802– 811、doi :10.1109/SFCS.1991.185452、ISBN 0-8186-2445-0、S2CID  209133。
  3. ^ ロバートソン、ニール；シーモア、PD；トーマス、ロビン（1993）「3次元空間におけるグラフのリンクレス埋め込み」アメリカ数学会誌、28（1）：84–89、arXiv：math/9301216、doi：10.1090/S0273-0979-1993-00335-5、MR  1164063、S2CID  1110662。
  4. ^ Béla Bollobás (1998) 『現代グラフ理論』、Springer、 ISBN 0-387-98488-79ページ
  5. ^ 柏原敏信 (1981)、「一部の交差グラフのアルゴリズム」、斉藤信次;西関隆雄編、グラフ理論とアルゴリズム、第 17 回東北大学電気通信研究所シンポジウム、仙台、1980 年 10 月 24 ～ 25 日、講演論文集、コンピュータサイエンス講義ノート、vol. 108、Springer-Verlag、pp.  171–181、doi : 10.1007/3-540-10704-5_15、ISBN 978-3-540-10704-0。
  6. ^ マリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマス(2006)、「強完全グラフ定理」(PDF)、Annals of Mathematics、164 (1): 51– 229、arXiv : math/0212070v1、doi :10.4007/annals.2006.164.51、S2CID  119151552。
  7. ^ Beineke、LW (1968)、「有向グラフの導出グラフ」、Sachs、H.;ヴォス、H.-J.ウォルター、H.-J. (編)、Beiträge zur Graphentheorie 、ライプツィヒ: Teubner、 17–33ページ 。
  8. ^ El-Mallah, Ehab; Colbourn, Charles J. (1988)、「いくつかのエッジ削除問題の複雑さ」、IEEE Transactions on Circuits and Systems、35 (3): 354– 362、Bibcode :1988ITCS...35..354E、doi :10.1109/31.1748。
  9. ^ 高見沢 功;西関 隆夫; 斉藤 信治 (1981)「直列並列グラフ上の組合せ問題」離散応用数学、3 (1): 75– 76、doi : 10.1016/0166-218X(81)90031-7。
  10. ^ Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977) , Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., pp.  311– 315, MR  0505860
  11. ^ Bodlaender, Hans L. (1998)、「木幅が制限されたグラフの部分kアーボレタム」、理論計算機科学、209 ( 1–2 ): 1–45、doi :10.1016/S0304-3975(97)00228-4、hdl : 1874/18312。
  12. ^ Bodlaender, Hans L. ; Thilikos, Dimitrios M. (1999)、「枝幅が最大3のグラフ」、Journal of Algorithms、32 (2): 167– 194、doi :10.1006/jagm.1999.1011、hdl : 1874/2734。
  13. ^ Seinsche, D. (1974)、「 n色グラフのクラスの性質について」、 Journal of Combinatorial Theory、シリーズB、16 (2): 191– 193、doi : 10.1016/0095-8956(74)90063-X、MR  0337679
  14. ^ ab Golumbic, Martin Charles (1978)、「自明に完璧なグラフ」、離散数学、24 (1): 105– 107、doi : 10.1016/0012-365X(78)90178-4。
  15. ^ Metelsky, Yury; Tyshkevich, Regina (1997)、「線形3-ユニフォームハイパーグラフの線グラフについて」、Journal of Graph Theory、25 (4): 243– 251、doi :10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K、MR  1459889
  16. ^ Jacobson, MS; Kézdy, Andre E.; Lehel, Jeno (1997)、「線形一様ハイパーグラフの交差グラフの認識」、Graphs and Combinatorics、13 (4): 359– 367、doi :10.1007/BF03353014、MR  1485929、S2CID  9173731
  17. ^ Naik, Ranjan N.; Rao, SB; Shrikhande, SS ; Singhi, NM (1982)、「k -uniform hypergraphs の交差グラフ」、European Journal of Combinatorics、3 : 159– 172、doi : 10.1016/s0195-6698(82)80029-2、MR  0670849
  18. ^ Yu, Yanming (2006)、「Ye-Delta-Ye の可約性に対するさらなる禁制マイナー」、The Electronic Journal of Combinatorics、13 R7、doi : 10.37236/1033Webサイト
  19. ^ Jiang, Zilin; Polyanskii, Alexandr (2020-03-01). 「有界スペクトル半径グラフの禁制部分グラフと等角線への応用」. Israel Journal of Mathematics . 236 (1): 393– 421. arXiv : 1708.02317 . doi :10.1007/s11856-020-1983-2. ISSN  1565-8511.