Combinatorial Theory

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.

Mathematics Subject Classifications: 05C31, 68W25

Keywords: Chromatic polynomial, acyclic orientation, complex zeros, broken circuit, maximum degree, claw-free graphs