On the location of chromatic zeros of series-parallel graphs

2022/04/21 by Bencs, Ferenc, Huijben, Jeroen, Regts, Guus · 1 citation
#05C31 (Primary) 05C15 #37F10 #82B20 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2204.10038

Abstract

In this paper we consider the zeros of the chromatic polynomial of series-parallel graphs. Complementing a result of Sokal, showing density outside the disk |q-1|≤1, we show density of these zeros in the half plane \Re(q)>3/2 and we show there exists an open region U containing the interval (0,32/27) such that U∖\1\ does not contain zeros of the chromatic polynomial of series-parallel graphs. We also disprove a conjecture of Sokal by showing that for each large enough integer Δ there exists a series-parallel graph for which all vertices but one have degree at most Δ and whose chromatic polynomial has a zero with real part exceeding Δ.

Cited by

• On the complex zeros and the computational complexity of approximating the reliability polynomial

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 zeros of the chromatic polynomial on bounded degree graphs
• Chromatic Polynomials and their Zeros and Asymptotic Limits for Families of Graphs
• On the zero-free region for the chromatic polynomial of graphs with maximum degree Δ and girth g