When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree

Abstract

Let $G$ be a simple graph with maximum degree $\Delta \ge 3$, and let $P(G,k)$ denote its chromatic polynomial. For each positive integer $k$, the list-color function $P_{\ell }(G,k)$ is the minimum number of $L$-colorings of $G$ over all $k$-assignments $L$. In this paper, we prove that $P_{\ell }(G,k)=P(G,k)$ for every integer $k\ge 23.41\Delta$. This gives a threshold for equality that is linear in the maximum degree and independent of the number of vertices or edges. It improves the known sufficient condition $k\ge |E(G)|-1$ for graphs with sufficiently many edges relative to their maximum degree.