New Proofs in Graph Minors

-
Paul Wollan, Sapienza University of Rome and Georgia Tech

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