Given a group $G$ of automorphisms of a graph $\Gamma$, the orbital chromatic polynomial $OP_{\Gamma,G}(x)$ is the polynomial whose value at a positive integer $k$ is the number of orbits of $G$ on proper $k$-colorings of $\Gamma.$ Cameron and Kayibi introduced this polynomial as a means of understanding roots of chromatic polynomials. In this light, they posed a problem asking whether 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 problem in a resounding negative by not only constructing a counterexample, but by providing a process for generating families of counterexamples. We additionally begin the program of finding classes of graphs whose orbital chromatic polynomials have real roots bounded above by the largest real root of their chromatic polynomials; in particular establishing this for many outerplanar graphs.
@article{10_37236_4412,
author = {Dae Hyun Kim and Alexander H. Mun and Mohamed Omar},
title = {Chromatic bounds on orbital chromatic roots},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/4412},
zbl = {1298.05121},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4412/}
}
TY - JOUR
AU - Dae Hyun Kim
AU - Alexander H. Mun
AU - Mohamed Omar
TI - Chromatic bounds on orbital chromatic roots
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/4412/
DO - 10.37236/4412
ID - 10_37236_4412
ER -
%0 Journal Article
%A Dae Hyun Kim
%A Alexander H. Mun
%A Mohamed Omar
%T Chromatic bounds on orbital chromatic roots
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4412/
%R 10.37236/4412
%F 10_37236_4412
Dae Hyun Kim; Alexander H. Mun; Mohamed Omar. Chromatic bounds on orbital chromatic roots. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4412
