{"id":{"repo_id":"lsu-thes","oai_identifier":"oai:repository.lsu.edu:gradschool_dissertations-1960"},"canonical_url":"https://search.dev.ndltd.org/etd/lsu-thes/oai:repository.lsu.edu:gradschool_dissertations-1960","repository":{"repo_id":"lsu-thes","name":"Lousiana State University","base_url":"https://repository.lsu.edu/do/oai/"},"display":{"title":"Unavoidable minors in graphs and matroids","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Chun, Carolyn Barlow"],"institution":"Mathematics","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Applied Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-01-01T08:00:00Z","date_published":"2009-01-01T08:00:00Z","updated_at":"2026-07-24T02:58:40Z","subjects":["unavoidable","minor","matroid","graph"],"languages":[],"rights":["unrestricted","Release the entire work immediately for access worldwide."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["etd-07092009-140417","https://repository.lsu.edu/gradschool_dissertations/961"],"render_values":[{"text":"etd-07092009-140417","href":null,"code":true},{"text":"https://repository.lsu.edu/gradschool_dissertations/961","href":"https://repository.lsu.edu/gradschool_dissertations/961","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.31390/gradschool_dissertations.961","outbound_label":"DOI","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Chun, Carolyn Barlow"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009-06-19"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-05-12T23:10:34Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Applied Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Mathematics"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["unavoidable","minor","matroid","graph"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["unrestricted","Release the entire work immediately for access worldwide."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["etd-07092009-140417","10.31390/gradschool_dissertations.961","https://repository.lsu.edu/gradschool_dissertations/961"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Unavoidable minors in graphs and matroids"]}]}],"canonical_facts":{"dc:creator":["Chun, Carolyn Barlow"],"dc:date":["2009-06-19"],"dc:date.available":["2022-05-12T23:10:34Z"],"dc:description.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."],"dc:identifier":["etd-07092009-140417","10.31390/gradschool_dissertations.961","https://repository.lsu.edu/gradschool_dissertations/961"],"dc:rights":["unrestricted","Release the entire work immediately for access worldwide."],"dc:subject":["unavoidable","minor","matroid","graph"],"dc:title":["Unavoidable minors in graphs and matroids"],"thesis:degree_discipline":["Applied Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"],"thesis:institution_name":["Mathematics"]},"updated_at":"2026-07-24T02:58:40Z"}