Bounds for the real zeros of chromatic polynomials

Abstract

Sokal in 2001 proved that the complex zeros of the chromatic polynomial PG(q) of any graph G lie in the disc |q| < 7.963907δ, where δ is the maximum degree of G. This result answered a question posed by Brenti, Royle and Wagner in 1994 and hence proved a conjecture proposed by Biggs, Damerell and Sands in 1972. Borgs gave a short proof of Sokal's result. Fernández and Procacci recently improved Sokal's result to |q| < 6.91δ. In this paper, we shall show that all real zeros of PG(q) are in the interval [0,5.664δ). For the special case that δ = 3, all real zeros of PG(q) are in the interval [0,4.765δ). © 2008 Cambridge University Press.