Unavoidable minors in graphs and matroids

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.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Applied Mathematics

Grantor

Mathematics

Year dc:date.available

2009

Author dc:creator

• Chun, Carolyn Barlow

• unavoidable
• minor
• matroid
• graph

Statement dc:rights

• unrestricted
• Release the entire work immediately for access worldwide.

Identifier

etd-07092009-140417
https://repository.lsu.edu/gradschool_dissertations/961

OAI identifier oai:identifier

oai:repository.lsu.edu:gradschool_dissertations-1960