Graph polynomials and group coloring of graphs
Bartłomiej Bosek, Jarosław Grytczuk, Grzegorz Gutowski, Oriol Serra, Mariusz Zając · European Journal of Combinatorics · 2022
Let Γ be an Abelian group and let G be a simple graph. We say that G is Γ-colorable if for some fixed orientation of G and every edge labeling ℓ:E(G)→Γ, there exists a vertex coloring c by the elements of Γ such that c(y)−c(x)≠ℓ(e), for every edge e=xy (oriented from x to y). Langhede and Thomassen proved recently that every planar graph on n vertices has at least 2n/9 different Z5-colorings. By using a different approach based on graph polynomials, we extend this result to K5-minor-free graphs in the more general setting of field coloring. More specifically, we prove that every such graph on n vertices is F-5-choosable, whenever F is an arbitrary field with at least 5 elements. Moreover, the number of colorings (for every list assignment) is at least 5n/4.