Show simple item record

dc.contributor.advisorThomas, Robin
dc.contributor.authorLiu, Chun-Hung
dc.date.accessioned2014-08-27T13:38:17Z
dc.date.available2014-08-27T13:38:17Z
dc.date.created2014-08
dc.date.issued2014-06-16
dc.date.submittedAugust 2014
dc.identifier.urihttp://hdl.handle.net/1853/52262
dc.description.abstractRobertson 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.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectGraph
dc.subjectTopological minor
dc.subjectWell-quasi-ordering
dc.titleGraph structures and well-quasi-ordering
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentMathematics
thesis.degree.levelDoctoral
dc.contributor.committeeMemberBaker, Matthew
dc.contributor.committeeMemberTovey, Craig A.
dc.contributor.committeeMemberTrotter, William
dc.contributor.committeeMemberYu, Xingxing
dc.date.updated2014-08-27T13:38:17Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record