- Series
- School of Mathematics Colloquium
- Time
- Thursday, October 20, 2016 - 11:05am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Xingxing Yu – Georgia Tech
- Organizer
- Shahaf Nitzan
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.