New Proofs in Graph Minors

-
Paul Wollan, Sapienza University of Rome and Georgia Tech
Fine Hall 224

The graph minor structure theorem of Robertson and Seymour gives an approximate characterization of graphs which do not contain a fixed graph $H$ as a minor. The theorem has numerous applications including Robertson and Seymour's proof for the disjoint paths algorithm as well as the proof of Wagner's conjecture that graphs are well-quasi-ordered under the minor relation. The original proof of the structure theorem is quite long and technical. We will discuss a new and simpler proof which makes the result more widely accessible. This is joint work with Kenichi Kawarabayashi