Orbital chromatic and flow roots

Peter J. Cameron*, K. K. Kayibi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

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 [57,00), Here we discuss the location of real orbital chromatic roots. We show, for example, that they are dense in ℝ, 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.

Original languageEnglish
Pages (from-to)401-407
Number of pages7
JournalCombinatorics Probability and Computing
Volume16
Issue number3
DOIs
Publication statusPublished - 1 May 2007

Fingerprint

Dive into the research topics of 'Orbital chromatic and flow roots'. Together they form a unique fingerprint.

Cite this