Graph minors – a survey

Summary

Abstract. We survey a number of results about minors of graphs which we have recently obtained. They are basically of three types:

1. (i) results concerning the structure of the graphs with no minor isomorphic to a fixed graph

2. (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

3. (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₁, G₂, … 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₁, …, s_k, t₁, …, t_k of G, whether there are k mutually disjoint paths P₁, …, 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.