View source for Forbidden graph characterization

{{short description|Describing a family of graphs by excluding certain (sub)graphs}}
{{Redirect-synonym|Forbidden minors|[[age restrictions]]}}

[[File:Simple bipartite graph; two layers.svg|thumb|The [[bipartite graph]]s, which can have their vertices partitioned into 2 sets such that no vertices in each set are adjacent to any other within the same set, are precisely described by the '''forbidden characterization''' of having no odd [[cycle graph]]s as subgraphs.]]

In [[graph theory]], a branch of mathematics, many important families of [[Graph (discrete mathematics)|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) [[Glossary_of_graph_theory#subgraph|subgraph]] or [[Graph minor|minor]].

A prototypical example of this phenomenon is [[Kuratowski's theorem]], which states that a graph is [[planar graph|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]] {{math|''K''{{sub|5}}}} and the [[complete bipartite graph]] {{math|''K''{{sub|3,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).

==Definition== 
More generally, a '''forbidden graph characterization''' is a method of [[characterization (mathematics)|specifying]] a family of [[graph (discrete mathematics)|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 <math>\mathcal{F}</math> [[if and only if]] a forbidden substructure is '''not''' contained in ''G''.  The '''forbidden substructure''' might be one of:
* [[Glossary of graph theory#subgraph|subgraph]]s, smaller graphs obtained from subsets of the vertices and edges of a larger graph,
* [[induced subgraph]]s, smaller graphs obtained by selecting a subset of the vertices and using all edges with both endpoints in that subset,
* [[Homeomorphism (graph theory)|homeomorphic]] subgraphs (also called [[topological minor]]s), smaller graphs obtained from subgraphs by collapsing paths of degree-two vertices to single edges, or
* [[graph minor]]s, smaller graphs obtained from subgraphs by arbitrary [[edge contraction]]s.
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 [[algorithm]]s 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 minor]]s, a family that is closed under minors always has a finite obstruction set.

==List of forbidden characterizations for graphs and hypergraphs==
{| class="wikitable"
|-
! Family
! Obstructions
! Relation
! Reference
|-
| rowspan=2 | [[Forest (graph theory)|Forest]]s
| Loops, pairs of parallel edges, and [[Cycle (graph theory)|cycles]] of all lengths
| Subgraph
| Definition
|-
| A loop (for multigraphs) or triangle ''K''<sub>3</sub> (for simple graphs)
| Graph minor
| Definition
|-
| [[Linear forest]]s
| [A loop / triangle ''K''<sub>3</sub> (see above)] and [[Star (graph theory)|star]] ''K''<sub>1,3</sub>
| Graph minor
| Definition
|-
| [[Claw-free graph]]s
| [[Star (graph theory)|Star]] ''K''<sub>1,3</sub>
| Induced subgraph
| Definition
|-
| [[Comparability graph]]s
| 
| Induced subgraph
| 
|-
| [[Triangle-free graph]]s
| Triangle ''K''<sub>3</sub>
| Induced subgraph
| Definition
|-
| rowspan=2 | [[Planar graph]]s
| ''K''<sub>5</sub> and ''K''<sub>3,3</sub>
| Homeomorphic subgraph
| [[Kuratowski's theorem]]
|-
| ''K''<sub>5</sub> and ''K''<sub>3,3</sub>
| Graph minor
| [[Wagner's theorem]]
|-
| [[Outerplanar graph]]s
| ''K''<sub>4</sub> and ''K''<sub>2,3</sub>
| Graph minor
| {{harvtxt|Diestel|2000}},<ref name="diestel">{{citation|first=Reinhard|last=Diestel|year=2000|author-link=Reinhard Diestel|title=Graph Theory|publisher= Springer-Verlag|isbn=0-387-98976-5|series=Graduate Texts in Mathematics|volume=173}}.</ref> [https://books.google.com/books?id=04YbQF8oscQC&lpg=PA327&pg=PA107 p. 107]
|-
| [[1-planar graph|Outer 1-planar graphs]]
| Six forbidden minors
| Graph minor
| {{harvtxt|Auer|Bachmaier|Brandenburg|Gleißner|2013}}<ref>{{citation
 | last1 = Auer | first1 = Christopher
 | last2 = Bachmaier | first2 = Christian
 | last3 = Brandenburg | first3 = Franz J.
 | last4 = Gleißner | first4 = Andreas
 | last5 = Hanauer | first5 = Kathrin
 | last6 = Neuwirth | first6 = Daniel
 | last7 = Reislhuber | first7 = Josef
 | editor1-last = Wismath | editor1-first = Stephen
 | editor2-last = Wolff | editor2-first = Alexander
 | contribution = Recognizing outer 1-planar graphs in linear time
 | doi = 10.1007/978-3-319-03841-4_10
 | pages = 107–118
 | series = Lecture Notes in Computer Science
 | title = 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers
 | volume = 8242
 | year = 2013
 | doi-access = free
 | isbn = 978-3-319-03840-7
 }}.</ref>
|-
| Graphs of fixed [[graph genus|genus]]
| A finite obstruction set
| Graph minor
| {{harvtxt|Diestel|2000}},<ref name="diestel"/> [https://books.google.com/books?id=NvRXJSl9hUUC&pg=RA1-PA275&vq=forbidden&dq=%22hereditary+property%22+forbidden p. 275]
|-
| [[Apex graph]]s
| A finite obstruction set
| Graph minor
| <ref>{{citation | last1 = Gupta | first1 = A. | last2 = Impagliazzo | first2 = R. | author2-link = Russell Impagliazzo | contribution = Computing planar intertwines | doi = 10.1109/SFCS.1991.185452 | pages = 802–811 | publisher = IEEE Computer Society | title = [[Symposium on Foundations of Computer Science|Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91)]] | contribution-url = http://www.cse.ucsd.edu/users/russell/arvind.ps | year = 1991| isbn = 0-8186-2445-0 | s2cid = 209133 }}.</ref>
|-
| [[Linkless embedding|Linklessly embeddable graphs]]
| The [[Petersen family]]
| Graph minor
| <ref>{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = P. D. | author2-link = Paul Seymour (mathematician) | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician) | doi = 10.1090/S0273-0979-1993-00335-5 | issue = 1 | journal = Bulletin of the American Mathematical Society | pages = 84–89 | title = Linkless embeddings of graphs in 3-space | volume = 28 | year = 1993 | arxiv = math/9301216 | mr = 1164063| s2cid = 1110662 }}.</ref>
|-
| [[Bipartite graph]]s
| Odd cycles
| Subgraph
| <ref>[[Béla Bollobás]] (1998) "Modern Graph Theory", Springer, {{ISBN|0-387-98488-7}} [https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA9&dq=bipartite+odd+cycle p. 9]</ref>
|-
| [[Chordal graph]]s
| Cycles of length 4 or more
| Induced subgraph
| <ref>{{citation | last = Kashiwabara | first = Toshinobu | contribution = Algorithms for some intersection graphs | doi = 10.1007/3-540-10704-5_15 | editor1-last = Saito | editor1-first = Nobuji | editor2-last = Nishizeki | editor2-link = Takao Nishizeki | editor2-first = Takao | pages = 171–181 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings | volume = 108 | year = 1981 | doi-access = free | isbn = 978-3-540-10704-0 }}.</ref>
|-
| [[Perfect graph]]s
| Cycles of odd length 5 or more or their [[complement graph|complements]]
| Induced subgraph
| <ref>{{citation
 | doi = 10.4007/annals.2006.164.51
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
 | last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
 | last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
 | journal = [[Annals of Mathematics]]
 | pages = 51–229
 | url = http://people.math.gatech.edu/~thomas/PAP/spgc.pdf
 | issue = 1
 | title = The strong perfect graph theorem
 | volume = 164
 | year = 2006
 | arxiv = math/0212070v1
 | s2cid = 119151552
 }}.</ref>
|-
| [[Line graph|Line graph of graph]]s
| [[Line graph#Characterization and recognition|9 forbidden subgraphs]]
| Induced subgraph
| <ref>{{citation
 | last = Beineke | first = L. W.
 | contribution = Derived graphs of digraphs
 | editor1-last = Sachs | editor1-first = H.
 | editor2-last = Voss | editor2-first = H.-J.
 | editor3-last = Walter | editor3-first = H.-J.
 | location = Leipzig
 | pages = 17–33
 | publisher = Teubner
 | title = Beiträge zur Graphentheorie
 | year = 1968
 }}.</ref>
|-
| [[Graph union]]s of [[cactus graph]]s
| The four-vertex ''[[diamond graph]]'' formed by removing an edge from the [[complete graph]] ''K''<sub>4</sub>
| Graph minor
| <ref>{{citation|last1=El-Mallah|first1=Ehab|last2=Colbourn|first2=Charles J.|author2-link=Charles Colbourn|title=The complexity of some edge deletion problems|journal=IEEE Transactions on Circuits and Systems|volume=35|issue=3|year=1988|pages=354–362|doi=10.1109/31.1748}}.</ref>
|-
| [[Ladder graph]]s
| ''K''<sub>2,3</sub> and its [[dual graph]]
| Homeomorphic subgraph
| <ref>{{citation | last1 = Takamizawa | first1 = K. | last2 = Nishizeki | author2-link = Takao Nishizeki | first2 = Takao | last3 = Saito | first3 = Nobuji | doi = 10.1016/0166-218X(81)90031-7 | issue = 1 | journal = Discrete Applied Mathematics | pages = 75–76 | title = Combinatorial problems on series–parallel graphs | volume = 3 | year = 1981| doi-access = free }}.</ref>
|-
| [[Split graph]]s
| <math>C_4, C_5, \bar{C}_4 \left(= K_2 + K_2\right)</math>
| Induced subgraph
| <ref>{{citation
 | last1 = Földes | first1 = Stéphane
 | last2 = Hammer | first2 = Peter Ladislaw | author2-link =Peter Ladislaw Hammer
 | contribution = Split graphs
 | title = Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)
 | pages = 311–315
 | series = Congressus Numerantium
 | volume = XIX
 | publisher = Utilitas Math.
 | location = Winnipeg
 | year = 1977a
 | mr = 0505860
 }}</ref>
|-
| 2-connected [[series–parallel graph|series–parallel]] ([[treewidth]] ≤&nbsp;2, [[branchwidth]]{{nbsp}}≤&nbsp;2)
| ''K''<sub>4</sub>
| Graph minor
| {{harvtxt|Diestel|2000}},<ref name="diestel"/> [https://books.google.com/books?id=04YbQF8oscQC&lpg=PA327&pg=PA327 p. 327]
|-
| [[Treewidth]] ≤&nbsp;3
| ''K''<sub>5</sub>, [[octahedron]], [[pentagonal prism]], [[Wagner graph]]
| Graph minor
| <ref>{{citation | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender | title = A partial ''k''-arboretum of graphs with bounded treewidth | journal = Theoretical Computer Science | volume = 209 | issue = 1–2 | pages = 1–45 | year = 1998 | doi = 10.1016/S0304-3975(97)00228-4| hdl = 1874/18312 | hdl-access = free }}.</ref>
|-
| [[Branchwidth]] ≤&nbsp;3
| ''K''<sub>5</sub>, [[octahedron]], [[cube]], [[Wagner graph]]
| Graph minor
| <ref>{{citation | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender | last2 = Thilikos | first2 = Dimitrios M. | doi = 10.1006/jagm.1999.1011 | issue = 2 | journal = Journal of Algorithms | pages = 167–194 | title = Graphs with branchwidth at most three | volume = 32 | year = 1999| hdl = 1874/2734 | hdl-access = free }}.</ref>
|-
| [[Cograph|Complement-reducible graphs (cographs)]]
| 4-vertex path ''P''<sub>4</sub>
| Induced subgraph
| <ref>{{Citation
 | last1=Seinsche | first1=D.
 | title=On a property of the class of ''n''-colorable graphs
 | mr=0337679
 | year=1974
 | journal=[[Journal of Combinatorial Theory]] | series=Series B
 | pages=191–193
 | issue=2
 | doi=10.1016/0095-8956(74)90063-X
 | volume=16
 | doi-access=free
 }}</ref>
|-
| [[Trivially perfect graph]]s
| 4-vertex path ''P''<sub>4</sub> and 4-vertex cycle ''C''<sub>4</sub>
| Induced subgraph
| <ref name="g78">{{citation
 | last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
 | doi = 10.1016/0012-365X(78)90178-4
 | issue = 1
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 105–107
 | title = Trivially perfect graphs
 | volume = 24
 | year = 1978
 | doi-access = free
 }}.</ref>
|-
| [[Threshold graph]]s
| 4-vertex path ''P''<sub>4</sub>, 4-vertex cycle ''C''<sub>4</sub>, and complement of ''C''<sub>4</sub>
| Induced subgraph
| <ref name="g78"/>
|-
| [[Line graph of a hypergraph|Line graph of 3-uniform linear hypergraph]]s
| A finite list of forbidden induced subgraphs with minimum degree at least 19
| Induced subgraph
| <ref>{{Citation
 | first1 = Yury | last1 = Metelsky
 | first2 = Regina | last2 = Tyshkevich | author2-link = Regina Tyshkevich
 | year = 1997 | title = On line graphs of linear 3-uniform hypergraphs
 | journal = [[Journal of Graph Theory]] | volume = 25
 | issue = 4 | pages = 243–251
 | mr = 1459889 | doi = 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K
 }}</ref>
|-
| [[Line graph of a hypergraph|Line graph of ''k''-uniform linear hypergraphs, ''k''&nbsp;>&nbsp;3]]
| A finite list of forbidden induced subgraphs with minimum edge degree at least 2''k''<sup>2</sup>&nbsp;−&nbsp;3''k''&nbsp;+&nbsp;1
| Induced subgraph
| <ref>{{citation
 | first1 = M. S. | last1 = Jacobson
 | first2 = Andre E. | last2 = Kézdy
 | first3 = Jeno | last3 = Lehel
 | title = Recognizing intersection graphs of linear uniform hypergraphs
 | journal = [[Graphs and Combinatorics]] | volume = 13 | pages = 359–367 | year = 1997
 | issue = 4
 | mr = 1485929
 | doi = 10.1007/BF03353014
 | s2cid = 9173731
 }}</ref><ref>{{citation
 | first1 = Ranjan N. | last1 = Naik
 | first2 = S. B. | last2 = Rao
 | first3 = S. S. | last3 = Shrikhande | authorlink3 = S. S. Shrikhande
 | first4 = N. M. | last4 = Singhi
 | title = Intersection graphs of ''k''-uniform hypergraphs
 | journal = [[European Journal of Combinatorics]] | volume = 3 | pages = 159–172 | year = 1982
 | mr = 0670849 | doi=10.1016/s0195-6698(82)80029-2
 | doi-access = free
 }}</ref>
|-
| Graphs [[Apex graph#YΔY-reducibility|ΔY-reducible]] to a single vertex
| A finite list of at least 68 billion distinct (1,2,3)-clique sums
| Graph minor
| <ref>{{citation
 | first1 = Yanming | last1 = Yu
 | title = More forbidden minors for wye-delta-wye reducibility
 | journal = The Electronic Journal of Combinatorics | volume = 13 | year = 2006
 | doi = 10.37236/1033 | doi-access = free
 }} [http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r7 Website]
</ref>
|-
|Graphs of [[spectral radius]] at most <math>\lambda</math>
|A finite obstruction set exists if and only if <math>\lambda < \sqrt{2 + \sqrt{5}}</math> and <math>\lambda \neq \beta_m^{1/2} + \beta_m^{-1/2}</math> for any <math>m \ge 2</math>, where <math>\beta_m</math> is the largest root of <math>x^{m+1} = 1 + x + \dots + x^{m-1}</math>.
|Subgraph / induced subgraph
|<ref>{{Cite journal |last1=Jiang |first1=Zilin |last2=Polyanskii |first2=Alexandr |date=2020-03-01 |title=Forbidden Subgraphs for Graphs of Bounded Spectral Radius, with Applications to Equiangular Lines |url=https://doi.org/10.1007/s11856-020-1983-2 |journal=[[Israel Journal of Mathematics]] |language=en |volume=236 |issue=1 |pages=393–421 |doi=10.1007/s11856-020-1983-2 |issn=1565-8511|arxiv=1708.02317 }}</ref>
|-
| [[Cluster graph]]s
| three-vertex path graph
| Induced subgraph
| 
|-
| colspan=4 style="font-weight:bold;" | General theorems
|-
| A family defined by an [[induced-hereditary property]]
| A, possibly non-finite, obstruction set
| Induced subgraph
|
|-
| A family defined by a [[minor-hereditary property]]
| A finite obstruction set
| Graph minor
| [[Robertson–Seymour theorem]]
<!--
|-
|
|
|
|
-->
|}

==See also==
*[[Erdős–Hajnal conjecture]]
*[[Forbidden subgraph problem]]
*[[Matroid minor]]
*[[Zarankiewicz problem]]

==References==
{{reflist|2}}

[[Category:Graph theory]]
[[Category:Graph minor theory]]
[[Category:Graph families]]
[[Category:Hypergraphs]]