In
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 conne ...
, a branch of mathematics, many important families of
graphs
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 ...
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
Minor may refer to:
* Minor (law), a person under the age of certain legal activities.
** A person who has not reached the age of majority
* Academic minor, a secondary field of study in undergraduate education
Music theory
*Minor chord
** Barb ...
.
A prototypical example of this phenomenon is
Kuratowski's theorem
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 subdivi ...
, which states that a graph is
planar
Planar is an adjective meaning "relating to a plane (geometry)".
Planar may also refer to:
Science and technology
* Planar (computer graphics), computer graphics pixel information from several bitplanes
* Planar (transmission line technologies), ...
(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 is c ...
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 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
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
, 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
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 bicondi ...
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 subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
s, smaller graphs obtained by selecting a subset of the vertices and using all edges with both endpoints in that subset,
*
homeomorphic
In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphi ...
subgraphs (also called
topological 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 if ...
s), 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 if ...
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 ide ...
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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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 is cl ...
proves that, for the particular case of
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 if ...
s, a family that is closed under minors always has a finite obstruction set.
List of forbidden characterizations for graphs and hypergraphs
See also
*
Erdős–Hajnal conjecture
In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.
...
*
Forbidden subgraph problem In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges \operatorname(n,G) an n-vertex graph can have such that it does not have a Glossary of graph theory#Subgraphs, subgr ...
*
Matroid minor
In the mathematical theory of matroids, a minor of a matroid ''M'' is another matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restriction ...
*
Zarankiewicz problem
The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size.. Reprint of 1978 Academi ...
References
{{reflist, 2
Graph theory
Graph minor theory
Graph families
Hypergraphs