# 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 K$_5$ and the complete bipartite graph K$_{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 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 ${\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

| Family | Obstructions | Relation | Reference |
| Forests | Loops, pairs of parallel edges, and cycles of all lengths | Subgraph | Definition |
| Forests | A loop (for multigraphs) or triangle K$_3$ (for simple graphs) | Graph minor | Definition |
| Linear forests | [A loop / triangle K$_3$ (see above)] and star K$_{1,3}$ | Graph minor | Definition |
| Claw-free graphs | Star K$_{1,3}$ | Induced subgraph | Definition |
| Comparability graphs | | Induced subgraph | |
| Triangle-free graphs | Triangle K$_3$ | Induced subgraph | Definition |
| Planar graphs | K$_5$ and K$_{3,3}$ | Homeomorphic subgraph | Kuratowski's theorem |
| Planar graphs | K$_5$ and K$_{3,3}$ | Graph minor | Wagner's theorem |
| Outerplanar graphs | K$_4$ and K$_{2,3}$ | Graph minor | Diestel (2000), p. 107 |
| Outer 1-planar graphs | Six forbidden minors | Graph minor | Auer et al. (2013) |
| Graphs of fixed genus | A finite obstruction set | Graph minor | Diestel (2000), p. 275 |
| Apex graphs | A finite obstruction set | Graph minor | |
| Linklessly embeddable graphs | The Petersen family | Graph minor | |
| Bipartite graphs | Odd cycles | Subgraph | |
| Chordal graphs | Cycles of length 4 or more | Induced subgraph | |
| Perfect graphs | Cycles of odd length 5 or more or their complements | Induced subgraph | |
| Line graph of graphs | 9 forbidden subgraphs | Induced subgraph | |
| Graph unions of cactus graphs | The four-vertex diamond graph formed by removing an edge from the complete graph K$_4$ | Graph minor | |
| Ladder graphs | K$_{2,3}$ and its dual graph | Homeomorphic subgraph | |
| Split graphs | $C_{4},C_{5},{\bar {C}}_{4}\left(=K_{2}+K_{2}\right)$ | Induced subgraph | |
| 2-connected series–parallel (treewidth ≤ 2, branchwidth ≤ 2) | K$_4$ | Graph minor | Diestel (2000), p. 327 |
| Treewidth ≤ 3 | K$_5$, octahedron, pentagonal prism, Wagner graph | Graph minor | |
| Branchwidth ≤ 3 | K$_5$, octahedron, cube, Wagner graph | Graph minor | |
| Complement-reducible graphs (cographs) | 4-vertex path P$_4$ | Induced subgraph | |
| Trivially perfect graphs | 4-vertex path P$_4$ and 4-vertex cycle C$_4$ | Induced subgraph | |
| Threshold graphs | 4-vertex path P$_4$, 4-vertex cycle C$_4$, and complement of C$_4$ | Induced subgraph | |
| Line graph of 3-uniform linear hypergraphs | A finite list of forbidden induced subgraphs with minimum degree at least 19 | Induced subgraph | |
| Line graph of k-uniform linear hypergraphs, k > 3 | A finite list of forbidden induced subgraphs with minimum edge degree at least 2k$^2$ − 3k + 1 | Induced subgraph | |
| Graphs ΔY-reducible to a single vertex | A finite list of at least 68 billion distinct (1,2,3)-clique sums | Graph minor | |
| Graphs of spectral radius at most $\lambda$ | A finite obstruction set exists if and only if $\lambda <{\sqrt {2+{\sqrt {5}}}}$ and $\lambda \neq \beta _{m}^{1/2}+\beta _{m}^{-1/2}$ for any $m\geq 2$, where $\beta _{m}$ is the largest root of $x^{m+1}=1+x+\dots +x^{m-1}$. | Subgraph / induced subgraph | |
| Cluster graphs | three-vertex path graph | Induced subgraph | |
| 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 |