Exponentially Many 4-List-Colorings of Triangle-Free Graphs on Surfaces

Tom Kelly, Luke Postle

Thomassen proved that every planar graph $G$ on $n$ vertices has at least $2^{n/9}$ distinct $L$-colorings if $L$ is a 5-list-assignment for $G$ and at least $2^{n/10000}$ distinct…