Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs

Ferenc Bencs, Guus Regts

Published 2025-05-07Version 1

We prove that for any graph $G$ the (complex) zeros of its chromatic polynomial, $\chi_G(x)$, lie inside the disk centered at $0$ of radius $4.25 \Delta(G)$, where $\Delta(G)$ denote the maximum degree of $G$. This improves on a recent result of Jenssen, Patel and the second author, who proved a bound of $5.94\Delta(G)$. We moreover show that for graphs of sufficiently large girth we can replace $4.25$ by $3.60$ and for claw-free graphs we can replace $4.25$ by $3.81$. Our proofs build on the ideas developed by Jenssen, Patel and the second author, adding some new ideas. A key novel ingredient for claw-free graphs is to use a representation of the coefficients of the chromatic polynomial in terms of the number of certain partial acyclic orientations.