The Kelmans-Seymour conjecture on subdivisions of $K_5$

School of Mathematics Colloquium
Thursday, October 20, 2016 - 11:05am
1 hour (actually 50 minutes)
Skiles 006
Georgia Tech
A well-known theorem of Kuratowski  (1930) in graph theory states that a graph is planar if, and only if, it does not contain a subdivision  of $K_5$ or $K_{3,3}$. Wagner (1937) gave a structural characterization of graphs containing no subdivision of $K_{3,3}$.  Seymour in 1977 and, independently, Kelmans in 1979 conjectured that if a graph does not contain a subdivision of $K_5$ then it must be planar or contain a set of at most 4 vertices whose removal results in a disconnected  graph.  In this talk, I will discuss additional background  on this conjecture (including connection to the Four Color Theorem), and outline our recent proof of this conjecture (joint work with Dawei He and Yan Wang).  I will also mention several problems that are related to this conjecture or related to our approach.