All HMC Faculty Publications and Research

Document Type

Article - preprint

Department

Mathematics (HMC)

2013

Abstract

Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OPΓ,G(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. In \cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in R, extending Thomassen's famous result (see \cite{Thomassen}) that chromatic roots are dense in [32/27,∞). Cameron et al \cite{Cameron} further conjectured that the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root of its chromatic polynomial. We resolve this conjecture in the negative, and provide a process for generating families of counterexamples. We additionally show that the answer is true for various classes of graphs, including many outerplanar graphs.

This is a pre-print from arXiv:

Kim, D., Mun, A.H., Omar, M., Chromatic brounds on orbital chromatic roots. http://arxiv.org/abs/1310.3792

Rights Information

© 2013 Dae Hyun Kim, Alexander H. Mun, and Mohamed Omar

COinS