Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Forbidden graph characterization
Describing a family of graphs by excluding certain (sub)graphs

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 at least one of these two graphs as a subgraph (in which case it does not belong to the planar graphs).

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Forbidden graph characterization yet.
We don't have any PDF documents related to Forbidden graph characterization yet.
We don't have any Books related to Forbidden graph characterization yet.
We don't have any archived web articles related to Forbidden graph characterization yet.

Definition

More generally, a forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures, by specifying substructures that are forbidden to exist 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 F {\displaystyle {\mathcal {F}}} if and only if a forbidden substructure is not contained in G. The forbidden substructure might be one of:

  • subgraphs, smaller graphs obtained from subsets of the vertices and edges of a larger graph,
  • induced subgraphs, smaller graphs obtained by selecting a subset of the vertices and using all edges with both endpoints in that subset,
  • homeomorphic subgraphs (also called topological minors), smaller graphs obtained from subgraphs by collapsing paths of degree-two vertices to single edges, or
  • graph minors, smaller graphs obtained from subgraphs by arbitrary edge contractions.

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

FamilyObstructionsRelationReference
ForestsLoops, pairs of parallel edges, and cycles of all lengthsSubgraphDefinition
A loop (for multigraphs) or triangle K3 (for simple graphs)Graph minorDefinition
Linear forests[A loop / triangle K3 (see above)] and star K1,3Graph minorDefinition
Claw-free graphsStar K1,3Induced subgraphDefinition
Comparability graphsInduced subgraph
Triangle-free graphsTriangle K3Induced subgraphDefinition
Planar graphsK5 and K3,3Homeomorphic subgraphKuratowski's theorem
K5 and K3,3Graph minorWagner's theorem
Outerplanar graphsK4 and K2,3Graph minorDiestel (2000),1 p. 107
Outer 1-planar graphsSix forbidden minorsGraph minorAuer et al. (2013)2
Graphs of fixed genusA finite obstruction setGraph minorDiestel (2000),3 p. 275
Apex graphsA finite obstruction setGraph minor4
Linklessly embeddable graphsThe Petersen familyGraph minor5
Bipartite graphsOdd cyclesSubgraph6
Chordal graphsCycles of length 4 or moreInduced subgraph7
Perfect graphsCycles of odd length 5 or more or their complementsInduced subgraph8
Line graph of graphs9 forbidden subgraphsInduced subgraph9
Graph unions of cactus graphsThe four-vertex diamond graph formed by removing an edge from the complete graph K4Graph minor10
Ladder graphsK2,3 and its dual graphHomeomorphic subgraph11
Split graphs C 4 , C 5 , C ¯ 4 ( = K 2 + K 2 ) {\displaystyle C_{4},C_{5},{\bar {C}}_{4}\left(=K_{2}+K_{2}\right)} Induced subgraph12
2-connected series–parallel (treewidth ≤ 2, branchwidth ≤ 2)K4Graph minorDiestel (2000),13 p. 327
Treewidth ≤ 3K5, octahedron, pentagonal prism, Wagner graphGraph minor14
Branchwidth ≤ 3K5, octahedron, cube, Wagner graphGraph minor15
Complement-reducible graphs (cographs)4-vertex path P4Induced subgraph16
Trivially perfect graphs4-vertex path P4 and 4-vertex cycle C4Induced subgraph17
Threshold graphs4-vertex path P4, 4-vertex cycle C4, and complement of C4Induced subgraph18
Line graph of 3-uniform linear hypergraphsA finite list of forbidden induced subgraphs with minimum degree at least 19Induced subgraph19
Line graph of k-uniform linear hypergraphs, k > 3A finite list of forbidden induced subgraphs with minimum edge degree at least 2k2 − 3k + 1Induced subgraph2021
Graphs ΔY-reducible to a single vertexA finite list of at least 68 billion distinct (1,2,3)-clique sumsGraph minor22
Graphs of spectral radius at most λ {\displaystyle \lambda } A finite obstruction set exists if and only if λ < 2 + 5 {\displaystyle \lambda <{\sqrt {2+{\sqrt {5}}}}} and λ ≠ β m 1 / 2 + β m − 1 / 2 {\displaystyle \lambda \neq \beta _{m}^{1/2}+\beta _{m}^{-1/2}} for any m ≥ 2 {\displaystyle m\geq 2} , where β m {\displaystyle \beta _{m}} is the largest root of x m + 1 = 1 + x + ⋯ + x m − 1 {\displaystyle x^{m+1}=1+x+\dots +x^{m-1}} .Subgraph / induced subgraph23
Cluster graphsthree-vertex path graphInduced subgraph
General theorems
A family defined by an induced-hereditary propertyA, possibly non-finite, obstruction setInduced subgraph
A family defined by a minor-hereditary propertyA finite obstruction setGraph minorRobertson–Seymour theorem

See also

References

  1. Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, ISBN 0-387-98976-5. 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 (eds.), 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8242, pp. 107–118, doi:10.1007/978-3-319-03841-4_10, ISBN 978-3-319-03840-7. 978-3-319-03840-7 ↩

  3. Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, ISBN 0-387-98976-5. 0-387-98976-5 ↩

  4. 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. 0-8186-2445-0 ↩

  5. 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, S2CID 1110662. /wiki/Neil_Robertson_(mathematician) ↩

  6. Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9 /wiki/B%C3%A9la_Bollob%C3%A1s ↩

  7. Kashiwabara, Toshinobu (1981), "Algorithms for some intersection graphs", in Saito, Nobuji; Nishizeki, Takao (eds.), 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, vol. 108, Springer-Verlag, pp. 171–181, doi:10.1007/3-540-10704-5_15, ISBN 978-3-540-10704-0. 978-3-540-10704-0 ↩

  8. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem" (PDF), Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070v1, doi:10.4007/annals.2006.164.51, S2CID 119151552. /wiki/Maria_Chudnovsky ↩

  9. Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J. (eds.), Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33. ↩

  10. 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. /wiki/Charles_Colbourn ↩

  11. 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. /wiki/Takao_Nishizeki ↩

  12. 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 /wiki/Peter_Ladislaw_Hammer ↩

  13. Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, ISBN 0-387-98976-5. 0-387-98976-5 ↩

  14. 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, hdl:1874/18312. /wiki/Hans_L._Bodlaender ↩

  15. 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, hdl:1874/2734. /wiki/Hans_L._Bodlaender ↩

  16. 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 /wiki/Journal_of_Combinatorial_Theory ↩

  17. Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics, 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4. /wiki/Martin_Charles_Golumbic ↩

  18. Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics, 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4. /wiki/Martin_Charles_Golumbic ↩

  19. 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 /wiki/Regina_Tyshkevich ↩

  20. Jacobson, M. S.; Kézdy, Andre E.; Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs", Graphs and Combinatorics, 13 (4): 359–367, doi:10.1007/BF03353014, MR 1485929, S2CID 9173731 /wiki/Graphs_and_Combinatorics ↩

  21. Naik, Ranjan N.; Rao, S. B.; Shrikhande, S. S.; Singhi, N. M. (1982), "Intersection graphs of k-uniform hypergraphs", European Journal of Combinatorics, 3: 159–172, doi:10.1016/s0195-6698(82)80029-2, MR 0670849 /wiki/S._S._Shrikhande ↩

  22. Yu, Yanming (2006), "More forbidden minors for wye-delta-wye reducibility", The Electronic Journal of Combinatorics, 13, doi:10.37236/1033 Website /wiki/Doi_(identifier) ↩

  23. Jiang, Zilin; Polyanskii, Alexandr (2020-03-01). "Forbidden Subgraphs for Graphs of Bounded Spectral Radius, with Applications to Equiangular Lines". Israel Journal of Mathematics. 236 (1): 393–421. arXiv:1708.02317. doi:10.1007/s11856-020-1983-2. ISSN 1565-8511. https://doi.org/10.1007/s11856-020-1983-2 ↩