Stan Dziobiak
Louisiana State University
Kuratowski-type Characterizations of certain classes of graphs
Abstract
A classical result of Kuratowski and Wagner states
that a graph $G$ is planar if and only if $K_5$ and $K_{3,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). 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 finding such obstruction
sets. In this talk, we will present certain classes of graphs for which
the obstruction sets are known.
Wednesday, February 9, 2011
3:30 – 4:30 P.M.
372 Science and Engineering Building
(Refreshments at 3:00-3:30 PM in the kitchen area adjacent to 368 SEB)