[1] The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.
The order in which a sequence of such contractions and deletions is performed on G does not affect the resulting graph H. Graph minors are often studied in the more general context of matroid minors.
In this context, it is common to assume that all graphs are connected, with self-loops and multiple edges allowed (that is, they are multigraphs rather than simple graphs); the contraction of a loop and the deletion of a cut-edge are forbidden operations.
A deep result by Neil Robertson and Paul Seymour states that this partial order is actually a well-quasi-ordering: 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.
Another equivalent way of stating this is that any set of graphs can have only a finite number of minimal elements under the minor ordering.
The Hadwiger conjecture has been proven for k ≤ 6,[14] but is unknown in the general case.
Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory."
Another result relating the four-color theorem to graph minors is the snark theorem announced by Robertson, Sanders, Seymour, and Thomas, a strengthening of the four-color theorem conjectured by W. T. Tutte and stating that any bridgeless 3-regular graph that requires four colors in an edge coloring must have the Petersen graph as a minor.
For example a minor-closed graph family F has bounded pathwidth if and only if its forbidden minors include a forest,[16] F has bounded tree-depth if and only if its forbidden minors include a disjoint union of path graphs, F has bounded treewidth if and only if its forbidden minors include a planar graph,[17] and F has bounded local treewidth (a functional relationship between diameter and treewidth) if and only if its forbidden minors include an apex graph (a graph that can be made planar by the removal of a single vertex).
However it is straightforward to construct finite forbidden topological minor characterizations from finite forbidden minor characterizations by replacing every branch set with k outgoing edges by every tree on k leaves that has down degree at least two.
In the case where a graph H can be obtained from a graph G by a sequence of lifting operations (on G) and then finding an isomorphic subgraph, we say that H is an immersion minor of G. There is yet another way of defining immersion minors, which is equivalent to the lifting operation.
In graph drawing, immersion minors arise as the planarizations of non-planar graphs: from a drawing of a graph in the plane, with crossings, one can form an immersion minor by replacing each crossing point by a new vertex, and in the process also subdividing each crossed edge into a path.
[27] An alternative and equivalent definition of a graph minor is that H is a minor of G whenever the vertices of H can be represented by a collection of vertex-disjoint subtrees of G, such that if two vertices are adjacent in H, there exists an edge with its endpoints in the corresponding two trees in G. An odd minor restricts this definition by adding parity conditions to these subtrees.
[28] The Hadwiger conjecture, that k-chromatic graphs necessarily contain k-vertex complete graphs as minors, has also been studied from the point of view of odd minors.
[30] The problem of deciding whether a graph G contains H as a minor is NP-complete in general; for instance, if H is a cycle graph with the same number of vertices as G, then H is a minor of G if and only if G contains a Hamiltonian cycle.
However, when G is part of the input but H is fixed, it can be solved in polynomial time.
More specifically, the running time for testing whether H is a minor of G in this case is O(n3), where n is the number of vertices in G and the big O notation hides a constant that depends superexponentially on H;[3] since the original Graph Minors result, this algorithm has been improved to O(n2) time.
[31] Thus, by applying the polynomial time algorithm for testing whether a given graph contains any of the forbidden minors, it is theoretically possible to recognize the members of any minor-closed family in polynomial time.
This result is not used in practice since the hidden constant is so huge (needing three layers of Knuth's up-arrow notation to express) as to rule out any application, making it a galactic algorithm.
[32] Furthermore, in order to apply this result constructively, it is necessary to know what the forbidden minors of the graph family are.