Georgia Institute of Technology College of Sciences

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.