- Series
- ACO Student Seminar
- Time
- Wednesday, April 15, 2009 - 1:30pm for 1 hour (actually 50 minutes)
- Location
- ISyE Executive Classroom
- Speaker
- Luke Postle – School of Mathematics/ACO, Georgia Tech
- Organizer
- Annette Rohrs
Grotzsch's Theorem states that every triangle-free planar graph is
3-colorable.
Thomassen conjectured that every triangle-free planar graph has
exponentially many distinct 3-colorings. He proved that it has at least
2^{n^{1/12}/20000} distinct 3-colorings where n is the number of vertices.
We show that it has at least 2^{\sqrt{n/600}} distinct 3-colorings.
Joint work with Arash Asadi and Robin Thomas.