Unbounded separation between orbital chromatic and chromatic roots

About 13 years old · traced to

Let N>0N>0. A graph Γ\Gamma has chromatic polynomial PΓ(x)P_{\Gamma}(x), and let GG be an automorphism group of Γ\Gamma. The orbital chromatic polynomial OPΓ,G(x)OP_{\Gamma,G}(x) is the polynomial associated with the action of GG on Γ\Gamma.

Unbounded separation conjecture. For any N>0N>0, there exists a graph Γ\Gamma and automorphism group GG of Γ\Gamma for which OPΓ,G(x)OP_{\Gamma,G}(x) has a root at least NN larger than the largest real root of PΓ(x)P_{\Gamma}(x).

This conjecture asks whether orbital chromatic roots can lie arbitrarily far to the right of the largest real chromatic root. The paper notes that orbital chromatic roots can exceed chromatic roots, but gives no resolution of whether their separation is unbounded.

References

Primary source

Dae Hyun Kim, Alexander H. Mun and Mohamed Omar, “Chromatic Bounds On Orbital Chromatic Roots”, arXiv:1310.3792 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.