2016/02/15 by Tom Kelly, Kelly, Tom, Luke Postle +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1602.04717
12 pages, 2 figures
arxiv created 2016/02/15 · arxiv updated 2016/02/16
Thomassen proved that every planar graph G on n vertices has at least 2n/9 distinct L-colorings if L is a 5-list-assignment for G and at least 2n/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 Σ of genus g, then there exist constants ε,cg > 0 such that if G has an L-coloring, then G has at least cg2ε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 ε,α>0 such that if G is a graph on n vertices embedded in a surface Σ of fixed genus g, H is a proper subgraph of G, and ϕ is an L-coloring of H that extends to an L-coloring of G, then ϕ extends to at least 2ε(n - α(g + |V(H)|)) 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 ε=(1)/(8), and α= 130.