Combinatorics, Probability and Computing


Orbital Chromatic and Flow Roots


a1 School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail:;


The chromatic polynomial PΓ(x) of a graph Γ is a polynomial whose value at the positive integer k is the number of proper k-colourings of Γ. If G is a group of automorphisms of Γ, then there is a polynomial OPΓ,G(x), whose value at the positive integer k is the number of orbits of G on proper k-colourings of Γ.

It is known that real chromatic roots cannot be negative, but they are dense in $\lsqb \frac{32}{27},$ ∞). Here we discuss the location of real orbital chromatic roots. We show, for example, that they are dense in $\mathbb{R}$, but under certain hypotheses, there are zero-free regions.

We also look at orbital flow roots. Here things are more complicated because the orbit count is given by a multivariate polynomial; but it has a natural univariate specialization, and we show that the roots of these polynomials are dense in the negative real axis.

(Received February 27 2006)