Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-02T20:12:43.877Z 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: [email protected]; [email protected])
K. K. KAYIBI
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: [email protected]; [email protected])
Get access Rights & Permissions [Opens in a new window]

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 ∞). 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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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