Chromatic Polynomial Evaluation Spectra

Abstract

Around 10 years ago, Agol and Krushkal showed that the number of chromatic polynomials $P_G$ arising from graphs $G$ on $n$ vertices grows exponentially with $n$, by establishing that the (dual) flow polynomial $F_G\left(\frac{3+\sqrt{5}}{2}\right)$ already takes on exponentially many values, if one varies $G$ over all planar cubic graphs $G$ on $n$ vertices. We show, more generally, that the size of the set $\{P_G(q):|V(G)|=n\}$ is exponential in $n$, for every fixed real number $q\ne 0,1,2$. In fact, our approach can also be pushed to show that $P_G(q)$ already takes on exponentially many values, if we only vary $G$ over all planar graphs on $n$ vertices. The case $q=3$ confirms a conjecture of Agol, which was initially motivated by the $\mathsf{NP}$-completeness of planar $3$-colorability.

20 pages, no figures, comments welcome!