Exponentially many 4-list-colorings of triangle-free graphs on surfaces

摘要

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 L-colorings if L is a 3-list-assignment for G and G has girth at least five. Postle and Thomas proved that if G is a graph on n vertices embedded on a surface Sigma of genus g, then there exist constants epsilon, c(g) 0 such that if G has an L-coloring, then G has at least c(g)2(epsilon n) distinct L-colorings if L is a 5-list-assignment for G or if L is a 3-list-assignment for G and G has girth at least five. More generally, they proved that there exist constants epsilon, alpha 0 such that if G is a graph on n vertices embedded in a surface Sigma of fixed genus g, H is a proper subgraph of G, and phi is an L-coloring of H that extends to an L-coloring of G, then phi extends to at least 2(epsilon(n-alpha(g+vertical bar V(H)vertical bar))) distinct L-colorings of G if L is a 5-list-assignment or if L is a 3-list-assignment and G has girth at least five. We prove the same result if G is triangle-free and L is a 4-list-assignment of G, where epsilon = 1/8, and alpha = 130.