A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-03262018-125736


Type of Document Dissertation
Author Gaslowitz, Joshua Zachary
Author's Email Address j.zachary.gaslowitz@vanderbilt.edu
URN etd-03262018-125736
Title Characterizations of Graphs Without Certain Small Minors
Degree PhD
Department Mathematics
Advisory Committee
Advisor Name Title
Mark Ellingham Committee Chair
Bruce Hughes Committee Member
Dong Ye Committee Member
Jerry Spinrad Committee Member
Mike Mihalik Committee Member
Paul Edelman Committee Member
Keywords
  • restricted minor
  • graph minor
Date of Defense 2018-03-19
Availability unrestricted
Abstract
This dissertation contributes new results about minor-restricted families of graphs to the field of structural graph theory. A graph G contains a graph H as a minor if H can be formed from G through a sequence of vertex deletions, edge deletions, and edge contractions. Graph minors are of interest in part because they often serve as obstructions to having important properties. For example, Wagner's Theorem characterizes graphs that can be embedded in the plane as exactly those which contain neither K5 nor K3,3 as minors.

It is known that the set of graphs embeddable in any fixed surface, and indeed each minor-closed set of graphs, has a similar characterization in terms of a finite list of forbidden minors --- though finding this list is, in general, very difficult. The related problem of fixing a graph H and describing the family of H-minor-free graphs is also difficult, although a very rough structural description that applies to any H is known. A precise characterization of such families has been found for several specific minors, sometimes with an additional constraint on the connectivity of the graphs. Our work provides a characterization and enumeration of 4-connected K2,5-minor-free graphs and a characterization of planar 4-connected DW6-minor-free graphs, where DW6 is the join of C6 with two independent vertices.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Gaslowitz-Dissertation.pdf 907.99 Kb 00:04:12 00:02:09 00:01:53 00:00:56 00:00:04

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.