- Series
- Graph Theory Seminar
- Time
- Thursday, February 14, 2013 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Paul Wollan – University of Rome and Georgia Tech
- Organizer
- Robin Thomas
The Weak Structure Theorem of Robertson and Seymour is the cornerstone of
many of the algorithmic applications of graph minors techniques. The
theorem states that any graph which has both large tree-width and excludes
a fixed size clique minor contains a large, nearly planar subgraph. In
this talk, we will discuss a new proof of this result which is
significantly simpler than the original proof of Robertson and Seymour. As
a testament to the simplicity of the proof, one can extract explicit
constants to the bounds given in the theorem. We will assume no previous
knowledge about graph minors or tree-width.
This is joint work with Ken Kawarabayashi and Robin Thomas