Foundations of the chromatic polynomial
Fengming Dong, Khee Meng Koh · 2022
The chromatic polynomial of a graph evaluated at λ gives the number of ways to properly color the graph with λ colors. It arose from the four color conjecture and in turn gave rise to the Tutte polynomial, which can be viewed as a two variable generalization of the chromatic polynomial. This chapter gives an overview of some of the central topics in the study of the chromatic polynomial. Computing the chromatic polynomial, including classes of graphs for which it can be computed in polynomial time. Properties of chromatic polynomials, such as interpretations of coefficients, factorizations, combinatorial interpretations, unimodality of coefficients, inequalities of chromatic polynomials, and encoding of graph connectivity. Identifying chromatically equivalent graphs, that is, graphs with the same chromatic polynomial. Significance and locations of the roots of chromatic polynomials.