Department of
Applied
Mathematics

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

Luke Postle

Georgia Tech

Abstract

(Joint work with A. Asadi and R. Thomas)

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.