TOPICS
Search

Chromatic Root-Free Interval


An interval in which no chromatic root exists for any possible chromatic polynomial is known as a chromatic root-free interval. An chromatic root-free interval that cannot be extended is known as a maximal chromatic root-free interval.

Chromatic roots on the real line and in the complex plane

(-infty,0) and (0,1) are maximal root-free intervals, as is (1,32/27] (Jackson 1993, Alikhani and Ghanbari 2024). Furthermore, chromatic roots are dense in the complex plane (Sokal 2004, Cameron and Morgan 2016). The plots above show a histogram of chromatic roots along the real axis and the positions of chromatic roots in the complex plane for graphs in GraphData (the latter of which shows clear deviations from uniformity).


See also

Chromatic Polynomial, Chromatic Root, Interval

Explore with Wolfram|Alpha

References

Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.Cameron, P. J. and Morgan, K. "Algebraic Properties of Chromatic Roots." 3 Oct 2016. https://arxiv.org/abs/1610.00424.Dong, F. M., Koh, K. M.; and Teo, K. L. Chromatic Polynomials and Chromaticity of Graphs. Singapore: World Scientific, 2005.Jackson, B. "A Zero Free Interval for Chromatic Polynomials of Graphs." Combin. Probab. Comput. 2, 325-336, 1993.Sokal, A. D. "Chromatic Roots Are Dense in the Whole Complex Plane." Combin. Probab. and Comput. 13, 221-261, 2004.

Cite this as:

Weisstein, Eric W. "Chromatic Root-Free Interval." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ChromaticRoot-FreeInterval.html

Subject classifications