2023/09/19 by Jenssen, Matthew, Patel, Viresh, Regts, Guus · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.10928
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 Kg 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 Kg Δ centered at 0, where Kg is the solution to a certain optimization problem. In particular, Kg < 5 when g ≥ 5 and Kg < 4 when g ≥ 25 and Kg 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.