Graph Structures and Well-Quasi-Ordering
Chun-Hung Liu
Georgia Institute of Technology, USA
Georgia Institute of Technology, USA
2014/07/29 Tuesday 4PM-5PM
Room 1409
Room 1409
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 1980’s 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 theorem 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.
of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that 
, and 
if and only if G contains 
. Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and 
if and only if G contains 
. They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that 
if and only if G contains 
. We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither 
(a