New Proofs in Graph Minors
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 wellquasiordered 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