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

Abstract

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)$ denotes the maximum degree of $G$. This improves on a recent result of Jenssen, Patel and Regts, who proved a bound of $5.94\Delta (G)$. Moreover, we 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 add some substantially novel ideas to those developed by Jenssen, Patel, and Regts, while building on them. 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.

21 pages. No major changes. Several small corrections based on two referee reports