Combinatorics, Probability and Computing



Paper

Chromatic Roots are Dense in the Whole Complex Plane


ALAN D. SOKAL a1 1
a1 Department of Physics, New York University, 4 Washington Place, New York, NY 10003, USA (e-mail: sokal@nyu.edu)

Article author query
sokal a   [Google Scholar] 
 

Abstract

I show that the zeros of the chromatic polynomials $P_G(q)$ for the generalized theta graphs $\Theta^{(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 roots 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.

(Published Online March 3 2004)
(Received December 29 2000)
(Revised August 12 2003)



Footnotes

1 This research was supported in part by US National Science Foundation grants PHY–9520978, PHY–9900769 and PHY–0099393. Some of the work took place during a Visiting Fellowship at All Souls College, Oxford, where it was supported in part by Engineering and Physical Sciences Research Council grant GR/M 71626 and aided by the warm hospitality of John Cardy and the Department of Theoretical Physics.