Configurations in Large t-connected Graphs

I will discuss a technique that allows us to establish the existence of certain configurations in large t-connected graphs, even though such configurations need not exist in small graphs. Two configurations of interest are complete minors and disjoint paths connecting prescribed pairs of vertices.

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 minor isomorphic to the complete graph on t vertices has a set of at most t-5 vertices whose deletion makes the graph planar. This is best possible, except for the value of N. We also prove that the k Disjoint Paths Problem is feasible in every sufficiently big (2k+3)-connected graph.

This is joint work with Sergey Norin.

Robin Thomas, Georgia Institute of Technology

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube