Breaking the degeneracy barrier for coloring graphs with no $K_t$ minors
- Series
- Graph Theory Seminar
- Time
- Tuesday, September 15, 2020 - 15:45 for 1 hour (actually 50 minutes)
- Location
- https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
- Speaker
- Zi-Xia Song – University of Central Florida – Zixia.Song@ucf.edu
Hadwiger's conjecture from 1943 states that every graph with no Kt minor is (t−1)-colorable for every t≥1. In the early 1980s, Kostochka and Thomason independently proved that every graph with no Kt minor has average degree O(t√logt) and hence is O(t√logt)-colorable. In this talk, we show that every graph with no Kt minor is O(t(logt)β)-colorable for every β>1/4, making the first improvement on the order of magnitude of the Kostochka-Thomason bound.
This is joint work with Sergey Norin and Luke Postle.