In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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.
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 Glossary of graph theory#Su ...
, 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 i ...
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 d ...
, 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 discret ...
, or
hypergraph
In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
, 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
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
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 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.
Definition
Formally, let G=(V,E) ...
s, smaller graphs obtained by selecting a subset of the vertices and using all edges with both endpoints in that subset,
*
homeomorphic
In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function betw ...
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, 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, 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 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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s for testing whether a graph belongs to a given family. In many cases, it is possible to test in
polynomial time
In theoretical 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 p ...
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 minors 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 ...
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, 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
*
Forbidden subgraph problem
*
Matroid minor
*
Zarankiewicz problem
References
{{reflist, 2
Graph theory
Graph minor theory
Graph families
Hypergraphs