Back to search

Georgia Institute of Technology

Graph structures and well-quasi-ordering

Abstract

dc:description.abstract

Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation. In other words, given infinitely many graphs, one graph contains another as a minor. An application of this theorem is that every property that is closed under deleting vertices, edges, and contracting 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, 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 a 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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Chun-Hung
Advisor dc:contributor.advisor
  • Thomas, Robin
Committee members dc:contributor.committeemember
  • Baker, Matthew
  • Tovey, Craig A.
  • Trotter, William
  • Yu, Xingxing

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/52262

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liu, Chun-Hung. Graph structures and well-quasi-ordering. Doctoral thesis, Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/52262