Chromatic roots are dense in the whole complex plane

2000/12/31 by Alan D. Sokal · 7 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Combinatorial Mathematics #Alias #Chromatic polynomial #Chromatic scale #Combinatorics #Complex plane #Corollary #Discrete mathematics #Geometry #Graph #Mathematical Dynamics and Fractals #Mathematical analysis #Mathematics #Partition (number theory) #Physics #Planar #Planar graph #Plane (geometry) #Potts model #Pure mathematics #Topological and Geometric Data Analysis #cond-mat.stat-mech #math-ph #math.CO #math.CV #math.MP

paper · pdf · doi:10.1017/s0963548303006023

published as Combin. Probab. Comput. 13, 221-261 (2004) · LaTeX2e, 53 pages. Version 2 includes a new Appendix B. Version 3 adds a new Theorem 1.4 and a new Section 5, and makes several small improvements. To appear in Combinatorics, Probability & Computing

arxiv created 2003/08/28 · openalex publication_date 2004/03/01 · arxiv updated 2021/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

I show that the zeros of the chromatic polynomials P_G(q) for the generalized theta graphs Θ^(s,p) are, taken together, dense in the whole complex plane with the possible exception of the disc |q-1| < 1. The same holds for their dichromatic polynomials (alias Tutte polynomials, alias Potts-model partition functions) Z_G(q,v) outside the disc |q+v| < |v|. An immediate corollary is that the chromatic zeros of not-necessarily-planar graphs are dense in the whole complex plane. The main technical tool in the proof of these results is the Beraha-Kahane-Weiss theorem on the limit sets of zeros for certain sequences of analytic functions, for which I give a new and simpler proof.

Citations

• The Beauty of Fractals
• Every planar map is four colorable. Part II: Reducibility
• Every planar map is four colorable. Part I: Discharging
• Modern Graph Theory
• An introduction to chromatic polynomials
• q colourings of the triangular lattice
• Zeroes of chromatic polynomials: A new approach to Beraha conjecture using quantum groups
• The Four-Colour Theorem
• A Zero-Free Interval for Chromatic Polynomials of Graphs
• Every planar map is four colorable
• Some generalized order-disorder transformations
• A Contribution to the Theory of Chromatic Polynomials
• A Determinant Formula for the Number of Ways of Coloring a Map

Cited by

• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Partition Function Zeros at First-Order Phase Transitions: A General Analysis
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Graph Polynomials and Their Applications I: The Tutte Polynomial
• On the imaginary parts of chromatic root
• Gale duality bounds for roots of polynomials with nonnegative coefficients
• Chromatic polynomial [wikipedia]