### Graph Structures and Well-Quasi-Ordering

- Series
- Dissertation Defense
- Time
- Thursday, June 12, 2014 - 10:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 269
- Speaker
- Chun-Hung Liu – Georgia Tech

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). An application of these theorems is
that every property that is closed under deleting vertices, edges, and
contracting (or "splitting off", respectively) edges can be
characterized by finitely many graphs, and hence can be decided in
polynomial time.
In this thesis we are concerned with the topological minor relation.
We say that a graph G contains another graph H as a topological
minor if H can be obtained from a subgraph of G by repeatedly
deleting a vertex of degree two and adding an edge incident with the
neighbors of the deleted vertex. 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.
This thesis consists of two main results. The first one is a structure theorem for
excluding a fixed graph as a topological minor, which is analogous to a cornerstone
result of Robertson and Seymour, who gave such structure for graphs that exclude a
fixed minor. Results for topological minors 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 the next theorem.
The second main result is a proof of Robertson's conjecture. As a
corollary, properties on certain graphs closed under deleting
vertices, edges, and "suppressing" vertices of degree two can be
characterized by finitely many graphs, and hence can be decided in
polynomial time.