TOPICS
Search

Chromatic Root


A root of a chromatic polynomial is known as a chromatic root (Dong et al. 2005, Alikhani and Ghanbari 2024). Chromatic roots are potentially complex.

Tutte (1970) showed that phi+1=phi^2 cannot be a chromatic root of any chromatic polynomial where, phi is the golden ratio, a result extended to phi^n for positive integer n (Alikhani and Peng 2009).

HarveyRoyleGraphs

In contrast, phi+2 is a possible chromatic root (Harvey and Royle 2020; e.g., the graphs depicted above), a result which can be extended to phi+n for integer n>=2 (Alikhani and Hasni 2012, Alikhani and Ghanbar 2024) using the result that if alpha is a chromatic root, then for any natural number n, alpha+n is also a chromatic root.

Sokal (2004) showed that chromatic roots are dense in the complex plane (Cameron and Morgan 2016).

Chromatic roots on the real line and in the complex plane

An interval in which no chromatic roots are possible is known as a chromatic root-free interval. 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-Free 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.Alikhani, S., Hasni, R. "Algebraic Integers as Chromatic and Domination Roots." Int. J. Combin., Article ID 780765, 2012.Alikhani, S. Peng, Y. H. "Chromatic Zeros and the Golden Ratio." Appl. Anal. Disc. Math. 3, 120-122, 2009.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.Harvey, D. J. and Royle, G. F. "Chromatic Roots at 2 and the Beraha Number B_(10)." J. Graph Th. 95, 445-456, 2020.Sokal, A. D. "Chromatic Roots Are Dense in the Whole Complex Plane." Combin. Probab. and Comput. 13, 221-261, 2004.Tutte, W. T. "On Chromatic Polynomials and the Golden Ratio." J. Combin. Theory, Ser. B 9, 289-296, 1970.

Cite this as:

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

Subject classifications