Sub-Exponentially Many 3-Colorings of Triangle-Free Planar

Series: 
ACO Student Seminar
Wednesday, April 15, 2009 - 13:30
1 hour (actually 50 minutes)
Location: 
ISyE Executive Classroom
,  
School of Mathematics/ACO, Georgia Tech
Organizer: 
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.