Graph structures and well-quasi-ordering

Series
Graph Theory Seminar
Time
Thursday, August 21, 2014 - 1:30pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chun-Hung Liu – Math, GT and Princeton University
Organizer
Robin Thomas
Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation and the weak immersion relation. In other words, given infinitely many graphs, one graph contains another as a minor (or a weak immersion, respectively). Unlike the relation of minor and weak immersion, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980s that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated. We will sketch the idea of our recent proof of this conjecture. In addition, we will give a structure theorem for excluding a fixed graph as a topological minor. Such structure theorems were previously obtained by Grohe and Marx and by Dvorak, but we push one of the bounds in their theorems to the optimal value. This improvement is needed for our proof of Robertson's conjecture. This work is joint with Robin Thomas.