• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Graph structures and well-quasi-ordering

    Thumbnail
    View/Open
    LIU-DISSERTATION-2014.pdf (757.5Kb)
    Date
    2014-06-16
    Author
    Liu, Chun-Hung
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1853/52262
    Collections
    • Georgia Tech Theses and Dissertations [23403]
    • School of Mathematics Theses and Dissertations [424]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology