Graph minors – a survey
Neil R. Robertson, Paul D. Seymour · Cambridge University Press eBooks · 1985
. We survey a number of results about minors of graphs which we have recently obtained. They are basically of three types: (i) results concerning the structure of the graphs with no minor isomorphic to a fixed graph (ii) results concerning a conjecture of K. Wagner. that for any infinite set of graphs one of its members is isomorphic to a minor of another. and (iii) algorithmic results concerning the DISJOINT CONNECTING PATHS problem. INTRODUCTION There are two fundamental questions which motivate the work we report on here. (A) ( K. Wagner's well-quasi-ordering conjecture). Is it true that for every infinite sequence G 1 , G 2 , … of graphs, there exist i, j with i < j such that G i is isomorphic to a minor of G j ? [Graphs in this paper are finite and may have loops or multiple edges. A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges.] (B) ( The DISJOINT CONNECTING PATHS problem). If k ≥ 0, is there a polynomially-bounded algorithm to decide, given a graph G and vertices s 1 , …, s k , t 1 , …, t k of G, whether there are k mutually disjoint paths P 1 , …, P k of G where P i has ends s i , t i (1 ≤ i ≤ k)? [Two paths are disjoint if they have no common vertices.] Some of the background to these questions is discussed in sections 2 and 3.