Kim, Dae Hyun and Mun, Alexander H. and Omar, Mohamed (2014) Chromatic Bounds on Orbital Chromatic Roots. Electronic Journal of Combinatorics, 21 (4). Art. No. P4.17. ISSN 1077-8926. https://resolver.caltech.edu/CaltechAUTHORS:20141201-101314782
|
PDF
- Published Version
See Usage Policy. 281kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20141201-101314782
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 Γ. 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.
Item Type: | Article | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
Additional Information: | © 2014 The Authors. Submitted: May 30, 2014; Accepted: Oct 10, 2014; Published: Oct 23, 2014. The authors express sincere thanks to the anonymous referees for providing a number of helpful suggestions to improve the presentation of this paper. Supported by Summer Undergraduate Research Fellowships at the California Institute of Technology. | ||||||
Funders: |
| ||||||
Issue or Number: | 4 | ||||||
Classification Code: | Mathematics Subject Classiffications: 05C15, 05C30, 05C31 | ||||||
Record Number: | CaltechAUTHORS:20141201-101314782 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20141201-101314782 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 52209 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | Jason Perez | ||||||
Deposited On: | 02 Dec 2014 00:26 | ||||||
Last Modified: | 03 Oct 2019 07:40 |
Repository Staff Only: item control page