Clique minors and linkages in large t-connected graphs

Robin Thomas
Georgia Institute of Technology

We prove that for every integer t there exists an integer N such that every t-connected graph on at least N vertices with no K_t minor has a set of at most t-5 vertices whose deletion makes the graph planar. This is best possible in the sense that neither t-connectivity nor the size of the deleted set can be lowered, and for t>7 some lower bound on the number of vertices is needed. We will also discuss similar result about disjoint paths. This is joint work with S. Norin.

Back to Combinatorics Tutorials