Title page for ETD etd-07092009-140417


Type of Document Dissertation
Author Chun, Carolyn Barlow
Author's Email Address chchchun@gmail.com
URN etd-07092009-140417
Title Unavoidable Minors in Graphs and Matroids
Degree Doctor of Philosophy (Ph.D.)
Department Mathematics
Advisory Committee
Advisor Name Title
James Oxley Committee Chair
Bogdan Oporowski Committee Member
Guoli Ding Committee Member
Len Richardson Committee Member
Robert Perlis Committee Member
Mort Naraghi-Pour Dean's Representative
Keywords
  • unavoidable
  • minor
  • matroid
  • graph
Date of Defense 2009-06-19
Availability unrestricted
Abstract
It is well known that every sufficiently large connected graph G has either a vertex of high degree or a long path. If we require G to be more highly connected, then we ensure the presence of more highly structured minors. In particular, for all positive integers k, every 2-connected graph G has a series minor isomorphic to a k-edge cycle or K_{2,k}. In 1993, Oxley, Oporowski, and Thomas extended this result to 3- and internally 4-connected graphs identifying all unavoidable series minors of these classes. Loosely speaking, a series minor allows for arbitrary edge deletions but only allows edges to be contracted when they meet a degree-2 vertex. Dually, a parallel minor allows for any edge contractions but restricts the deletion of edges to those that lie in 2-edge cycles. This dissertation begins by proving the dual results to those noted above. These identify all unavoidable parallel minors for finite graphs of low connectivity. Following this, corresponding results on unavoidable minors for infinite graphs are proved. The dissertation concludes by finding the unavoidable parallel minors for 3-connected regular matroids, which combines the results for unavoidable series and parallel minors for graphs with Seymour's decomposition theorem for regular matroids.
Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  chun_diss.pdf 605.94 Kb 00:02:48 00:01:26 00:01:15 00:00:37 00:00:03

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.