Explicit Bounds for the Weak Structure Theorem

Graph Theory Seminar
Thursday, February 14, 2013 - 12:05pm
1 hour (actually 50 minutes)
Skiles 005
University of Rome and Georgia Tech
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