graph theory 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'' (also called ''nodes'' or ''points'') which are conn ...

, 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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

and the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

. For Kuratowski's theorem, the notion of containment is that of

graph homeomorphism In graph theory, two graphs G and G' are homeomorphic if there is a graph isomorphism from some subdivision of G to some subdivision of G'. If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually dep ...

, 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 Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

, 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

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bi ...

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 minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...

s, smaller graphs obtained from subgraphs by arbitrary

edge contraction In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...

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 In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s for testing whether a graph belongs to a given family. In many cases, it is possible to test in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

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 In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that i ...

proves that, for the particular case of

s, a family that is closed under minors always has a finite obstruction set.

List of forbidden characterizations for graphs and hypergraphs

References

{{reflist, 2 Graph theory Graph minor theory Graph families Hypergraphs

Definition

List of forbidden characterizations for graphs and hypergraphs

See also

References