Skip to content

Research at St Andrews

Orbital chromatic and flow roots

Research output: Contribution to journalArticle

Author(s)

Peter J. Cameron, K. K. Kayibi

School/Research organisations

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.

Close

Details

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

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. On the connectivity and independence number of power graphs of groups

    Cameron, P. J. & Jafari, S., 31 Mar 2020, In : Graphs and Combinatorics. First Online, 10 p.

    Research output: Contribution to journalArticle

  2. Substitutes for the non-existent square lattice designs for 36 varieties

    Bailey, R. A., Cameron, P. J., Soicher, L. H. & Williams, E. R., 4 Mar 2020, In : Journal of Agricultural, Biological and Environmental Statistics. First Online

    Research output: Contribution to journalArticle

  3. The Hall–Paige conjecture, and synchronization for affine and diagonal groups

    Bray, J., Cai, Q., Cameron, P. J., Spiga, P. & Zhang, H., Mar 2020, In : Journal of Algebra. 545, p. 27-42

    Research output: Contribution to journalArticle

  4. Appendage to: Multi-part balanced incomplete-block designs

    Bailey, R. A. & Cameron, P. J., 29 Oct 2019, In : Statistical Papers. First Online, 2 p.

    Research output: Contribution to journalArticle

  5. Association schemes for diagonal groups

    Cameron, P. J. & Eberhard, S., 27 Oct 2019, In : Australasian Journal of Combinatorics. 75, 3, p. 357-364

    Research output: Contribution to journalArticle

Related by journal

  1. Growing at a Perfect Speed

    Albert, M. H. & Linton, S. A., May 2009, In : Combinatorics, Probability and Computing. 18, 3, p. 301-308 8 p.

    Research output: Contribution to journalArticle

  2. Enumeration schemes for restricted permutations

    Vatter, V., Jan 2008, In : Combinatorics, Probability and Computing. 17, 1, p. 137-159 23 p.

    Research output: Contribution to journalArticle

  3. Homomorphism-homogeneous relational structures

    Cameron, P. J. & Nešetřil, J., 1 Jan 2006, In : Combinatorics Probability and Computing. 15, 1-2, p. 91-103 13 p.

    Research output: Contribution to journalArticle

  4. Connectedness, Classes and Cycle Index

    Bender, E. A., Cameron, P. J., Odlyzko, A. M. & Richmond, L. B., 1 Jan 1999, In : Combinatorics Probability and Computing. 8, 1-2, p. 31-43 13 p.

    Research output: Contribution to journalArticle

ID: 255495240

Top