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 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 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.

Family | Obstructions | Relation | Reference |
---|---|---|---|

Forests | loops, pairs of parallel edges, and cycles of all lengths | subgraph | Definition |

a loop (for multigraphs) or a triangle K_{3} (for simple graphs) | 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 |

K_{5} and K_{3,3} | graph minor | Wagner's theorem | |

Outerplanar graphs | K_{4} and K_{2,3} | graph minor | Diestel (2000),^{ [1] } p. 107 |

Outer 1-planar graphs | six 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 K_{4} | graph minor | ^{ [9] } |

Ladder graphs | K_{2,3} and its dual graph | homeomorphic subgraph | ^{ [10] } |

Split graphs | induced subgraph | ^{ [11] } | |

2-connected series-parallel (treewidth ≤ 2, branchwidth ≤ 2) | K_{4} | graph minor | Diestel (2000),^{ [1] } p. 327 |

Treewidth ≤ 3 | K_{5}, octahedron, pentagonal prism, Wagner graph | graph minor | ^{ [12] } |

Branchwidth ≤ 3 | K_{5}, octahedron, cube, Wagner graph | graph minor | ^{ [13] } |

Complement-reducible graphs (cographs) | 4-vertex path P_{4} | induced subgraph | ^{ [14] } |

Trivially perfect graphs | 4-vertex path P_{4} and 4-vertex cycle C_{4} | induced subgraph | ^{ [15] } |

Threshold graphs | 4-vertex path P_{4}, 4-vertex cycle C_{4}, and complement of C_{4} | induced subgraph | ^{ [15] } |

Line graph of 3-uniform linear hypergraphs | a finite list of forbidden induced subgraphs with minimum degree at least 19 | induced subgraph | ^{ [16] } |

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 | ^{ [17] }^{ [18] } |

Graphs ΔY-reducible to a single vertex | a finite list of at least 68 billion distinct (1,2,3)-clique sums | graph minor | ^{ [19] } |

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 |

In mathematics, **graph theory** is the study of *graphs*, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of *vertices* which are connected by *edges*. A distinction is made between **undirected graphs**, where edges link two vertices symmetrically, and **directed graphs**, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

In graph theory, a **planar graph** is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a **plane graph** or **planar embedding of the graph**. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, **Kuratowski's theorem** is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of *K*_{5} or of *K*_{3,3}.

In graph theory, the **Robertson–Seymour theorem** states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph *K*_{5} or the complete bipartite graph *K*_{3,3} as minors.

In graph theory, an **outerplanar graph** is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In graph theory, an undirected graph *H* is called a **minor** of the graph *G* if *H* can be formed from *G* by deleting edges and vertices and by contracting edges.

In the mathematical area of graph theory, a **clique** is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

In the mathematical discipline of graph theory, the **line graph** of an undirected graph *G* is another graph L(*G*) that represents the adjacencies between edges of *G*. L(*G*) is constructed in the following way: for each edge in *G*, make a vertex in L(*G*); for every two edges in *G* that have a vertex in common, make an edge between their corresponding vertices in L(*G*).

In the mathematical field of graph theory, a **snark** is a simple, connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, the connectivity is redundant so that removing no one edge would split the graph, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. In order to avoid trivial cases, snarks are often restricted to have girth at least 5.

In mathematics, a **universal graph** is an infinite graph that contains *every* finite graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family F: that is, an infinite graph belonging to *F* that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

In mathematics, a **dense graph** is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a **sparse graph**. The distinction between sparse and dense graphs is rather vague, and depends on the context.

In graph theory, **Wagner's theorem** is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither *K*_{5} nor *K*_{3,3}. This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

In graph theory, the **treewidth** of an undirected graph is a number associated with the graph. Treewidth may be defined in several equivalent ways: the size of the largest vertex set in a tree decomposition of the graph, the size of the largest clique in a chordal completion of the graph, the maximum order of a haven describing a strategy for a pursuit-evasion game on the graph, or the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

In graph theory, a **path decomposition** of a graph *G* is, informally, a representation of *G* as a "thickened" path graph, and the **pathwidth** of *G* is a number that measures how much the path was thickened to form *G*. More formally, a path-decomposition is a sequence of subsets of vertices of *G* such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as **interval thickness**, **vertex separation number**, or **node searching number**.

In graph theory, a **branch-decomposition** of an undirected graph *G* is a hierarchical clustering of the edges of *G*, represented by an unrooted binary tree *T* with the edges of *G* as its leaves. Removing any edge from *T* partitions the edges of *G* into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The **branchwidth** of *G* is the minimum width of any branch-decomposition of *G*.

In mathematics, the **graph structure theorem** is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

In graph theory, a **Trémaux tree** of an undirected graph *G* is a spanning tree of *G*, rooted at one of its vertices, with the property that every two adjacent vertices in *G* are related to each other as an ancestor and descendant in the tree. All depth-first search trees and all Hamiltonian paths are Trémaux trees. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called **normal spanning trees**, especially in the context of infinite graphs.

In combinatorial mathematics, an **Apollonian network** is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In graph theory, a **planar cover** of a finite graph *G* is a finite covering graph of *G* that is itself a planar graph. Every graph that can be embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers.

In graph theory, a family of graphs is said to have **bounded expansion** if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, **polynomial expansion**, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.

- 1 2 3 Diestel, Reinhard (2000),
*Graph Theory*, Graduate Texts in Mathematics,**173**, Springer-Verlag, ISBN 0-387-98976-5 . - ↑ 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,**8242**, pp. 107–118, doi: 10.1007/978-3-319-03841-4_10 . - ↑ 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 . - ↑ 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 . - ↑ Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9
- ↑ 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,**108**, Springer-Verlag, pp. 171–181, doi:10.1007/3-540-10704-5\_15 . - ↑ 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 . - ↑ 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. - ↑ 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 . - ↑ 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 . - ↑ 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,**XIX**, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860 - ↑ 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 . - ↑ 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 . - ↑ 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 - 1 2 Golumbic, Martin Charles (1978), "Trivially perfect graphs",
*Discrete Mathematics*,**24**(1): 105–107, doi:10.1016/0012-365X(78)90178-4 .. - ↑ 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 - ↑ Jacobson, M. S.; Kézdy, Andre E.; Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs",
*Graphs and Combinatorics*,**13**: 359–367, doi:10.1007/BF03353014, MR 1485929 - ↑ 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 - ↑ Yu, Yanming (2006), "More Forbidden Minors for Wye-Delta-Wye Reducibility",
*The Electronic Journal of Combinatorics*,**13**Website

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.