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


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.