Combinatorics, Probability and Computing

Paper

Orbital Chromatic and Flow Roots

PETER J. CAMERONa1 and K. K. KAYIBIa1

a1 School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: P.J.Cameron@qmul.ac.uk; kokokayibi@yahoo.co.uk)

Abstract

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)