On excluded and unavoidable minors in graphs
Document Type
Lecture
Publication Date
2-10-2014
Abstract
A classical result of Kuratowski and Wagner states that a graph G is planar if and only if K5 and K3;3 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). It is widely regarded as the starting point of graph minor theory. In the mid 80’s, Robertson and Seymour proved one of the deepest theorems in combinatorics, known as the Graph Minor Theorem (GMT): in any infinite 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 finite 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, and progress on the characterization of a bigger class, namely that of apex-series-parallel 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" (2014). Colloquium. 28.
https://egrove.olemiss.edu/math_colloquium/28
