On the zero-free region for the chromatic polynomial of graphs with maximum degree Δ and girth g

2024/09/20 by Fialho, Paula M. S., Juliano, Emanuel, Procacci, Aldo
#05C31 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2409.13892

Abstract

The purpose of the present paper is to provide, for all pairs of integers (Δ,g) with \D≥ 3 and g≥ 3, a positive number C(Δ, g) such that chromatic polynomial P_G(q) of a graph G with maximum degree Δ and finite girth g is free of zero if |q|≥ C(Δ, g). Our bounds enlarge the zero-free region in the complex plane of P_G(q) in comparison to previous bounds. In particular, for small values of \D our estimates yield a sensible improvement on the bounds recently obtained by Jenssen, Patel and Regts in \citeJPR, while they coincide with those of \citeJPR when Δ→ ∞.

Related

• Regions without complex zeros for chromatic polynomials on graphs with bounded degree
• Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
• Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
• Improved bounds for zeros of the chromatic polynomial on bounded degree graphs
• Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path