Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K5 and the complete bipartite graph K3,3. For Kuratowski's theorem, the notion of containment is that of graph homeomorphism, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing (in which case it belongs to the family of planar graphs) or it has a subdivision of one of these two graphs as a subgraph (in which case it does not belong to the planar graphs).

More generally, a forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures, by specifying substructures that are forbidden from existing within any graph in the family. Different families vary in the nature of what is forbidden. In general, a structure G is a member of a family \mathcal{F} if and only if a forbidden substructure is not contained in G. The forbidden substructure might be one of:

The set of structures that are forbidden from belonging to a given graph family can also be called an obstruction set for that family.

Forbidden graph characterizations may be used in algorithms for testing whether a graph belongs to a given family. In many cases, it is possible to test in polynomial time whether a given graph contains any of the members of the obstruction set, and therefore whether it belongs to the family defined by that obstruction set.

In order for a family to have a forbidden graph characterization, with a particular type of substructure, the family must be closed under substructures. That is, every substructure (of a given type) of a graph in the family must be another graph in the family. Equivalently, if a graph is not part of the family, all larger graphs containing it as a substructure must also be excluded from the family. When this is true, there always exists an obstruction set (the set of graphs that are not in the family but whose smaller substructures all belong to the family). However, for some notions of what a substructure is, this obstruction set could be infinite. The Robertson–Seymour theorem proves that, for the particular case of graph minors, a family that is closed under minors always has a finite obstruction set.

List of forbidden characterizations for graphs and hypergraphs

This list is incomplete; you can help by expanding it.
Family Forbidden graphs Relation Reference
Forests loops, pairs of parallel edges, and cycles of all lengths subgraph Definition
a loop (for multigraphs) or a triangle K3 (for simple graphs) graph minor Definition
Claw-free graphs star K1,3 induced subgraph Definition
Comparability graphs induced subgraph
Triangle-free graphs triangle K3 induced subgraph Definition
Planar graphs K5 and K3,3 homeomorphic subgraph Kuratowski's theorem
K5 and K3,3 graph minor Wagner's theorem
Outerplanar graphs K4 and K2,3 graph minor Diestel (2000),[1] p. 107
Outer 1-planar graphs five forbidden minors graph minor Auer et al. (2013)[2]
Graphs of fixed genus a finite obstruction set graph minor Diestel (2000),[1] p. 275
Apex graphs a finite obstruction set graph minor [3]
Linklessly embeddable graphs The Petersen family graph minor [4]
Bipartite graphs odd cycles subgraph [5]
Chordal graphs cycles of length 4 or more induced subgraph [6]
Perfect graphs cycles of odd length 5 or more or their complements induced subgraph [7]
Line graph of graphs nine forbidden subgraphs (listed here) induced subgraph [8]
Graph unions of cactus graphs the four-vertex diamond graph formed by removing an edge from the complete graph K4 graph minor [9]
Ladder graphs K2,3 and its dual graph homeomorphic subgraph [10]
Helly circular-arc graphs induced subgraph [11]
split graphs C_4, C_5, \bar{C_4} (=K_2+K_2) induced subgraph [12]
series-parallel (treewidth ≤ 2 branchwidth ≤ 2) K4 graph minor Diestel (2000),[1] p. 327
treewidth ≤ 3 K5, octahedron, pentagonal prism, Wagner graph graph minor [13]
branchwidth ≤ 3 K5, octahedron, cube, Wagner graph graph minor [14]
Complement-reducible graphs (cographs) 4-vertex path P4 induced subgraph [15]
Trivially perfect graphs 4-vertex path P4 and 4-vertex cycle C4 induced subgraph [16]
Threshold graphs 4-vertex path P4, 4-vertex cycle C4, and complement of C4 induced subgraph [16]
Line graph of 3-uniform linear hypergraphs a finite list of forbidden induced subgraphs with minimum degree at least 19 induced subgraph [17]
Line graph of k-uniform linear hypergraphs, k > 3 a finite list of forbidden induced subgraphs with minimum edge degree at least 2k2 − 3k + 1 induced subgraph [18][19]
General theorems
a family defined by an induced-hereditary property a (not necessarily finite) obstruction set induced subgraph
a family defined by an minor-hereditary property a finite obstruction set graph minor Robertson–Seymour theorem

See also

References

  1. ↑ 1.0 1.1 1.2 Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics 173, Springer-Verlag, ISBN 0-387-98976-5.
  2. ↑ Auer, Christopher; Bachmaier, Christian; Brandenburg, Franz J.; Gleißner, Andreas; Hanauer, Kathrin; Neuwirth, Daniel; Reislhuber, Josef (2013), "Recognizing outer 1-planar graphs in linear time", in Wismath, Stephen; Wolff, Alexander, 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, Lecture Notes in Computer Science 8242, pp. 107–118, doi:10.1007/978-3-319-03841-4_10.
  3. ↑ 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.
  4. ↑ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR 1164063.
  5. ↑ Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9
  6. ↑ Kashiwabara, Toshinobu (1981), "Algorithms for some intersection graphs", in Saito, Nobuji; Nishizeki, Takao, Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings, Lecture Notes in Computer Science 108, Springer-Verlag, pp. 171–181, doi:10.1007/3-540-10704-5\_15.
  7. ↑ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics 164 (1): 51–229, arXiv:math/0212070v1, doi:10.4007/annals.2006.164.51.
  8. ↑ Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.
  9. ↑ El-Mallah, Ehab; Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems 35 (3): 354–362, doi:10.1109/31.1748.
  10. ↑ Takamizawa, K.; Nishizeki, Takao; Saito, Nobuji (1981), "Combinatorial problems on series-parallel graphs", Discrete Applied Mathematics 3 (1): 75–76, doi:10.1016/0166-218X(81)90031-7.
  11. ↑ Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), "Linear-Time Recognition of Helly Circular-Arc Models and Graphs", Algorithmica 59 (2): 215–239, doi:10.1007/s00453-009-9304-5
  12. ↑ Földes, Stéphane; Hammer, Peter L. (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860
  13. ↑ Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4.
  14. ↑ Bodlaender, Hans L.; Thilikos, Dimitrios M. (1999), "Graphs with branchwidth at most three", Journal of Algorithms 32 (2): 167–194, doi:10.1006/jagm.1999.1011.
  15. ↑ Seinsche, D. (1974), "On a property of the class of n-colorable graphs", Journal of Combinatorial Theory, Series B 16 (2): 191–193, doi:10.1016/0095-8956(74)90063-X, MR 0337679
  16. ↑ 16.0 16.1 Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4..
  17. ↑ Metelsky, Yury; Tyshkevich, Regina (1997), "On line graphs of linear 3-uniform hypergraphs", 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
  18. ↑ Jacobson, M. S.; Kézdy, Andre E.; Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs", Graphs and Combinatorics 13: 359–367, MR 1485929
  19. ↑ Naik, Ranjan N.; Rao, S. B.; Shrikhande, S. S.; Singhi, N. M. (1982), "Intersection graphs of k-uniform hypergraphs", European J. Combinatorics 3: 159–172, doi:10.1016/s0195-6698(82)80029-2, MR 0670849