Graph Polynomials and Group Coloring of Graphs

Abstract

Let $\Gamma$ be an Abelian group and let $G$ be a simple graph. We say that $G$ is $\Gamma$-colorable if for some fixed orientation of $G$ and every edge labeling $\ell :E(G)\to \Gamma$, there exists a vertex coloring $c$ by the elements of $\Gamma$ such that $c(y)-c(x)\ne \ell (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 $2^{n/9}$ different ${\mathbb{Z}}_5$-colorings. By using a different approach based on graph polynomials, we extend this result to $K_5$-minor-free graphs in the more general setting of field coloring. More specifically, we prove that every such graph on $n$ vertices is $\mathbb{F}$-$5$-choosable, whenever $\mathbb{F}$ is an arbitrary field with at least $5$ elements. Moreover, the number of colorings (for every list assignment) is at least $5^{n/4}$.

14 pages