Abstract
I show that the zeros of the chromatic polynomials PG(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) ZG(q,v) outside the disc |3q + 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.
Original language | English (US) |
---|---|
Pages (from-to) | 221-261 |
Number of pages | 41 |
Journal | Combinatorics Probability and Computing |
Volume | 13 |
Issue number | 2 |
DOIs | |
State | Published - Mar 2004 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics