Minor (graph theory)
From Wikipedia, the free encyclopedia
 |
This article is missing citations or needs footnotes. Please help add inline citations to guard against copyright violations and factual inaccuracies. (January 2009) |
In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. An edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it used to connect. Equivalently, H is a minor of G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, and deleting some isolated vertices. The order in which a sequence of such contractions and deletions is performed on G does not affect the resulting graph H.
In the following example, graph H is a minor of graph G:
H. 
G. 
The following diagram illustrates this. First construct a subgraph of G by deleting the dashed edges (and the resulting isolated vertex), and then contract the gray edge (merging the two vertices it connects):
The relation "being a minor of" is a partial order on the isomorphism classes of graphs. As consequence of this fact we may say that, if I is a minor of H and H is a minor of G, then I is a minor of G.
Graph minors are often studied in the more general context of matroid minors. As such, it is common to assume all graphs to be connected, with loops and multiple edges allowed, and where the contraction of a loop and the deletion of a cut-edge are forbidden operations. In the above example, one of the deleted edges was a cut-edge, but we could have avoided this awkwardness by contracting that edge instead of deleting it. In some settings (such as with the study of pseudoforests) it makes sense to allow the deletion of a cut-edge, but one should be aware that such an operation will decrease the rank of the graph.
[edit] Major results and conjectures
A deep result by Neil Robertson and Paul Seymour states that if an infinite list G1, G2,... of finite graphs is given, then there always exist two indices i < j such that Gi is a minor of Gj. In the course of their proof, Seymour and Robertson also prove the graph structure theorem in which they determine, for any fixed graph H, the rough structure any graph which does not have H as a minor. Their theory establishes fundamental connections between graph minors and topological embeddings of graphs. For example a graph H is planar if and only if there exists an integer w such that every graph having tree width at least w contains H as a minor. Another consequence of their work is that the problem of deciding whether an input graph contains H as a minor can be solved in polynomial time for any fixed graph H.
The unsolved Hadwiger conjecture in graph theory proposes that if a graph G does not contain a minor isomorphic to the complete graph on n vertices, then G has a proper coloring with n colors.
[edit] Minor-closed graph families
Many classes of graphs can be characterized by "forbidden minors": a graph belongs to the class if and only if it does not have a minor from a certain specified list. The best-known example is Wagner's theorem characterizing the planar graphs as the graphs having neither K5 nor K3,3 as minors.
Classes of graphs described in this way have the property that every minor of a graph in F is also in F; such a class is said to be minor-closed. The general situation is described by the Robertson-Seymour theorem, stating that any minor-closed family is characterized by a finite set of forbidden minors. If F is minor-closed and does not contain all graphs, then every graph in F must be sparse.
Notable minor-closed graph families include:
- Planar graphs and outerplanar graphs
- Graphs that can be embedded on any fixed two-dimensional manifold
- Forests and pseudoforests
- Cactus graphs
- Apex graphs, formed by adding a single vertex to a planar graph
- Knotless and linkless embeddable graphs
- Graphs with a feedback vertex set of size bounded by some fixed constant
- Graphs with Colin de Verdière graph invariant bounded by some fixed constant
- Graphs with treewidth bounded by some fixed constant
- Graphs embeddable in R3 without knotted cycles
