The excluded minor structure theorem, and linkages in large graphs of bounded tree-width

Abstract

A central part of the graph minor theory developed by Robertson and Seymour is the excluded minor structure theorem. This theorem has found many applications elsewhere.

In the first part of this dissertation, we present a new version of this structure theorem with the goal to provide a broad feature set and an accessible terminology to allow for easier applications.

A graph G with |G|≥2k is called k-linked if for every choice of distinct vertices s_1,...,s_k,t_1,...,t_k there are disjoint paths P_1,...,P_k such that the ends of P_i are s_i and t_i. It has been shown by Larman and Mani and Jung that there exists a function f(k) such that every f(k)-connected graph is k-linked. Bollobàs and Thomason have given a linear bound of 22k. This result has been improved by Thomas and Wollan by proving that 10k-connected graphs are k-linked.

In the second part, we show that for all integers k and w there is an integer N such that every 2k+3-connected graph G of tree-width less than w on at least N vertices is k-linked. A central part of the proof is the study of certain subgraphs of G. We analyze linear decompositions of these subgraphs with new techniques we derived from those techniques used in the first part.