On the List Color Function Threshold

Abstract

The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the number of proper $m$-colorings of $G$. The list color function of graph $G$, denoted $P_{\ell }(G,m)$, is a list analogue of the chromatic polynomial that has been studied since the early 1990s, primarily through comparisons with the corresponding chromatic polynomial. It is known that for any graph $G$ there is a $k\in \mathbb{N}$ such that $P_{\ell }(G,m)=P(G,m)$ whenever $m\ge k$. The list color function threshold of $G$, denoted $\tau (G)$, is the smallest $k\ge \chi (G)$ such that $P_{\ell }(G,m)=P(G,m)$ whenever $m\ge k$. In 2009, Thomassen asked whether there is a universal constant $\alpha$ such that for any graph $G$, $\tau (G)\le {\chi }_{\ell }(G)+\alpha$, where ${\chi }_{\ell }(G)$ is the list chromatic number of $G$. We show that the answer to this question is no by proving that there exists a constant $C$ such that $\tau (K_{2,l})-{\chi }_{\ell }(K_{2,l})\ge C\sqrt{l}$ for $l\ge 16$.

11 pages