Graph minors - a survey. (English) Zbl 0568.05025

Surveys in combinatorics 1985, Pap. 10th Br. Combin. Conf., Glasgow/Scotl. 1985, Lond. Math. Soc. Lect. Note Ser. 103, 153-171 (1985).
[For the entire collection see Zbl 0561.00003.]
This paper is a survey of the results recently obtained by the authors the details of which are to be found in 9 papers, only three of which have yet been published, and apparently more are forthcoming. Most of these results concern the following two problems:
The conjecture of Wagner, stating that in any infinite sequence of graphs, at least one is isomorphic to a minor of another. Here a graph H is a minor of a graph G if G topologically contains a copy of H, i.e. H can be obtained from a subgraph of G by contraction of edges.
The disjoint connecting paths problem, asking for a polynomial algorithm to decide whether in a graph there exist k vertex-disjoint paths connecting given k origins to given k endpoints. The authors claim to have proven affirmatively both problems, although the details have yet to be checked. This paper gives an outline of the steps the authors went through in the process. The most well-known result concerning minors is the theorem of Kuratowski-Wagner, that there are exactly two minor- minimal nonplanar graphs: the complete graph \(K_ 5\), and the complete bipartite graph \(K_{3,3}\). It has now been shown that for any surface the list of minor-minimal not embeddable graphs is finite. Also both problems cited above have been proven right for graphs with given maximum genus. The techniques used are structure theorems, i.e. results stating that graphs without some ”useful” minor have a very restrictive nature, which is qualified. Several such structure theorems are cited and it is shown how these have direct consequences on both problems.
Reviewer: F.Plastria


05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity


Zbl 0561.00003