### DIMACS - Graduate Student Combinatorics Seminar

Title: Planarity and Wagner's Conjecture

Speaker: **Emilie Hogan**, Rutgers University

Date: Wednesday, April 15, 2009 12:00pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:
Kuratowski and Wagner's theorems give us a characterization of planar
graphs by forbidden minors and topological minors. The fact that we have
such a characterization (by a finite number of forbidden minors!) is
quite surprising. Wagner's conjecture is a generalization of this to
other surfaces and says that given any surface, the graphs that can be
embedded are characterized by finitely many forbidden minors. Eventually
Paul Seymour and Neil Robertson proved Wagner's conjecture with the
Graph Minor Theorem. I will talk about the proof of Kuratowski and
Wagner's planarity theorems, and how the Graph Minor Theorem proves
Wagner's big conjecture.