Document Type
Lecture
Publication Date
3-22-2013
Abstract
A classical result of Kuratowski and Wagner states that a graph G is planar if and only if K5 and K33 are not minors of G. (A minor of a graph G is a graph obtained from G by any sequence of the following operations: contracting edges, deleting edges, and deleting vertices). In the mid 80s, Robertson and Seymour proved one of the deepest theorems in combinatorics, known as the Graph Minor Theorem (GMT): in any innite set of graphs, at least one graph is a minor of another. Equivalently, a class of graphs is closed under minors if and only if it has a nite number of excluded minors (known as the obstruction set for the class). Knowing the obstruction set for a given minor-closed class of graphs is important as it allows for a polynomial-time algorithm to test membership in the class. Unfortunately the proof of the GMT is non-constructive, and hence gives no method of nding such obstruction sets. In this talk, we will present certain classes of graphs for which the obstruction sets are known, including our characterization of apex-outerplanar graphs. We will also discuss some results on unavoidable minors in graphs, including our result on the sizes of the unavoidable minors in 3-connected graphs.
Relational Format
presentation
Recommended Citation
Dziobiak, Stan, "On Excluded and Unavoidable Minors in Graphs" (2013). Combinatorics Seminar. 58.
https://egrove.olemiss.edu/math_combinatorics/58
