Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T02:44:55.371Z Has data issue: false hasContentIssue false
  • English
  • Français

Orbital Chromatic and Flow Roots

Published online by Cambridge University Press:  01 May 2007

PETER J. CAMERON  and
K. K. KAYIBI
PETER J. CAMERON
Affiliation:
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)
K. K. KAYIBI
Affiliation:
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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 3 , May 2007 , pp. 401 - 407
Copyright
Copyright © Cambridge University Press 2006

References

[1]Cameron, P. J., Jackson, B. and Rudd, J. Orbit-counting polynomials for graphs and codes. Discrete Math., submitted.Google Scholar
[2]Jackson, B. (1993) A zero-free interval for chromatic polynomials of graphs. Combin. Probab. Comput. 2 325–336.CrossRefGoogle Scholar
[3]Jackson, B. (2003) Zeros of chromatic and flow polynomials of graphs. J. Geom. 76 95–109.CrossRefGoogle Scholar
[4]Sokal, A. D. (2004) Chromatic roots are dense in the whole complex plane. Combin. Probab. Comput. 13 221–261.CrossRefGoogle Scholar
[5]Thomassen, C. (1997) The zero-free intervals for chromatic polynomials of graphs. Combin. Probab. Comput. 6 497–506.CrossRefGoogle Scholar
[6]Tutte, W. T. (1950) On the imbedding of linear graphs in surfaces. Proc. London Math. Soc. 51 474–483.Google Scholar
[7]Wakelin, C. D. (1994) Chromatic polynomials. PhD thesis, University of Nottingham.Google Scholar