Combinatorics Seminar
by Paul Seymour (Princeton University)
Abstract: Two old theorems of Robertson and Seymour say:
(1) For any forest H, the graphs with no H minor have bounded path-width (and for any non-forest H, they don't).
(2) For any planar graph H, the graphs with no H minor have bounded tree-width (and for any non-planar H, they don't).
What about results in between these? E.g., what happens if we exclude a series-parallel graph? In joint work with Maria Chudnovsky, Julien Codsi, Alex Divoux and Liana Yepremyan, we have been studying this and found some pretty theorems, which will be surveyed in this talk.
