Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem

09/19/2023
by   Matthew Jenssen, et al.
0

We prove that for any graph G of maximum degree at most Δ, the zeros of its chromatic polynomial χ_G(x) (in ℂ) lie inside the disc of radius 5.94 Δ centered at 0. This improves on the previously best known bound of approximately 6.91Δ. We also obtain improved bounds for graphs of high girth. We prove that for every g there is a constant K_g such that for any graph G of maximum degree at most Δ and girth at least g, the zeros of its chromatic polynomial χ_G(x) lie inside the disc of radius K_g Δ centered at 0, where K_g is the solution to a certain optimization problem. In particular, K_g < 5 when g ≥ 5 and K_g < 4 when g ≥ 25 and K_g tends to approximately 3.86 as g →∞. Key to the proof is a classical theorem of Whitney which allows us to relate the chromatic polynomial of a graph G to the generating function of so-called broken-circuit-free forests in G. We also establish a zero-free disc for the generating function of all forests in G (aka the partition function of the arboreal gas) which may be of independent interest.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset