Minor of a graph

Let $ G $ be a graph (possibly with loops and multiple edges). A minor of $ G $ is any graph obtained by a succession of the following operations:

i) deletion of a single edge;

ii) contraction of a single edge;

iii) removal of an isolated vertex.

The graph minor theorem of N. Robertson and P.D. Seymour says the following. Given an infinite sequence $ G _ {1} , G _ {2} \dots $ of finite graphs, there are indices $ i < j $ such that $ G _ {i} $ is (isomorphic to) a minor of $ G _ {j} $. This was conjectured by K. Wagner (Wagner's well-quasi-ordering conjecture).

Let $ P $ be any property of a graph which is closed under taking minors. For instance, the property of being imbeddable in a compact Riemann surface. Let $ L $ be the set of all minor-minimal isomorphism classes of graphs not possessing property $ P $. Then the graph minor theorem says that $ L $ is finite. This implies that property $ P $ is characterized by saying that a graph has property $ P $ if and only if it does not contain a minor from the finite set $ L $. In the case of the property "planar" the set $ L $ is given by the two graphs $ K _ {3,3} $ and $ K _ {5} $, cf. Kuratowski graph.

The finite forms of the graph minor theorem are as follows:

a) For all $ k $ there is an $ n $ such that for $ n $- tuples of graphs $ G _ {1} \dots G _ {n} $ with $ | G _ {i} | \leq k + i $ there is a pair $ i < j $ with $ G _ {i} $ isomorphic to a minor of $ G _ {j} $. Here $ | G _ {i} | $ denotes the sum of the number of vertices and the number of edges of $ G _ {i} $.

b) For all $ k $ there is an $ n $ such that for all $ n $- tuples of graphs $ G _ {1} \dots G _ {n} $ with $ | G _ {i} | \leq i $ there are $ i _ {1} < \dots < i _ {k} $ such that $ G _ {i _ {j} } $ is isomorphic to a minor of $ G _ {i _ {j+} 1 } $ for all $ j = 1 \dots k - 1 $.

Wagner's conjecture does not hold, in general, for infinite graphs, in the sense that there is a sequence of infinite graphs $ G _ {1} , G _ {2} \dots $ such that for all $ i \neq j $, $ G _ {i} $ is not a minor of $ G _ {j} $. The conjecture is open (1988) for countable graphs.

A consequence (application) is that each graph property that is closed under taking minors can be tested in polynomial time. So, for instance, planarity can be tested in polynomial time. Further, there exists a polynomial-time algorithm for the following problem: Given a graph $ G $ and vertices $ r _ {1} , s _ {1} \dots r _ {k} , s _ {k} $ of $ G $, find paths $ P _ {1} \dots P _ {k} $ so that $ P _ {i} $ connects $ r _ {i} $ and $ s _ {i} $ for all $ i = 1 \dots k $ and such that the $ P _ {1} \dots P _ {k} $ are vertex disjoint. Such problems arise in VLSI design.

References

[a1]	H. Friedman, N. Robertson, P.D. Seymour, "The metamathematics of the graph minor theorem" Logic and combinatorics (ed. S.G. Simpson) Contemporary Math. 65, Amer. Math. Soc. (1987) pp. 229–261 Zbl 0635.03060
[a2]	N. Robertson, P.D. Seymour, "Graph minors - a survey" I. Anderson (ed.) , Surveys in Combinatorics 1985 , Cambridge Univ. Press (1985) pp. 153–171 Zbl 0568.05025
[a3]	R. Thomas, "A counter-example to "Wagner's conjecture" for infinite graphs" Math. Proc. Cambridge Philos. Soc. , 103 (1988) pp. 55–57 Zbl 0647.05054