Chromatic bounds on orbital chromatic roots

zbMATH Open1298.05121arXiv1310.3792MaRDI QIDQ463065FDOQ463065

Authors: Dae Hyun Kim, Alexander H. Mun, Mohamed Omar 

Publication date: 23 October 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Given a group $G$ of automorphisms of a graph $Gamma$, the orbital chromatic polynomial $O{P}_{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.$ In cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in $mathbbR$, extending Thomassen's famous result (see cite{Thomassen}) that chromatic roots are dense in $[frac3227,infty)$. 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.

Full work available at URL: https://arxiv.org/abs/1310.3792

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Orbital Chromatic and Flow Roots
• Chromatic polynomials of oriented graphs
• Roots of chromatic polynomials
• Chromatic roots and minor-closed families of graphs
• Algebraic properties of chromatic roots

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

Cites Work

• The Zero-Free Intervals for Chromatic Polynomials of Graphs
• Title not available (Why is that?)
• Chromatic Roots are Dense in the Whole Complex Plane
• A Zero-Free Interval for Chromatic Polynomials of Graphs
• Chromatic Polynomials
• Planar triangulations with real chromatic roots arbitrarily close to 4
• Orbital Chromatic and Flow Roots

Cited In (2)

• Relations and bounds for the zeros of graph polynomials using vertex orbits
• Orbital Chromatic and Flow Roots

This page was built for publication: Chromatic bounds on orbital chromatic roots

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463065)