Chromatic bounds on orbital chromatic roots

MaRDI QIDQ463065zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1310.3792, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p17

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• A Zero-Free Interval for Chromatic Polynomials of Graphs
• Chromatic Polynomials
• Chromatic Roots are Dense in the Whole Complex Plane
• Orbital Chromatic and Flow Roots
• Planar triangulations with real chromatic roots arbitrarily close to 4
• The Zero-Free Intervals for Chromatic Polynomials of Graphs

Cited in

(2)

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

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)