TOPICS

# Chromatic Polynomial

The chromatic polynomial of an undirected graph , also denoted (Biggs 1973, p. 106) and (Godsil and Royle 2001, p. 358), is a polynomial which encodes the number of distinct ways to color the vertices of (where colorings are counted as distinct even if they differ only by permutation of colors). For a graph on vertices that can be colored in ways with no colors, way with one color, ..., and ways with colors, the chromatic polynomial of is defined as the unique Lagrange interpolating polynomial of degree through the points , , ..., . Evaluating the chromatic polynomial in variables at the points , 2, ..., then recovers the numbers of 1-, 2-, ..., and -colorings. In fact, evaluating at integers still gives the numbers of -colorings.

The chromatic polynomial is called the "chromial" for short by Bari (1974).

The chromatic number of a graph gives the smallest number of colors with which a graph can be colored, which is therefore the smallest positive integer such that (Skiena 1990, p. 211).

For example, the cubical graph has 1-, 2-, ... k-coloring counts of 0, 2, 114, 2652, 29660, 198030, 932862, 3440024, ... (OEIS A140986), resulting in chromatic polynomial

 (1)

Evaluating at , 2, ... then gives 0, 2, 114, 2652, 29660, 198030, 932862, 3440024, ... as expected.

A root of a chromatic polynomial is known as a chromatic root and an interval containing no chromatic root is called a chromatic root-free interval.

The chromatic polynomial of a graph in the variable can be determined in the Wolfram Language using ChromaticPolynomial[g, x]. Precomputed chromatic polynomials for many named graphs can be obtained using GraphData[graph, "ChromaticPolynomial"][z].

The chromatic polynomial is multiplicative over graph components, so for a graph having connected components , , ..., the chromatic polynomial of itself is given by

 (2)

The chromatic polynomial for a forest on vertices, edges, and with connected components is given by

 (3)

For a graph with vertex count and connected components, the chromatic polynomial is related to the rank polynomial and Tutte polynomial by

 (4) (5)

(extending Biggs 1993, p. 106). The chromatic polynomial of a planar graph is related to the flow polynomial of its dual graph by

 (6)

Chromatic polynomials are not diagnostic for graph isomorphism, i.e., two nonisomorphic graphs may share the same chromatic polynomial. A graph that is determined by its chromatic polynomial is said to be a chromatically unique graph; nonisomorphic graphs sharing the same chromatic polynomial are said to be chromatically equivalent.

Chromatic polynomials of the ladder graph and grid graph are considered by Yadav et al. (2024). The following table summarizes the chromatic polynomials for some simple graphs. Here is the falling factorial.

 graph chromatic polynomial barbell graph book graph centipede graph complete graph cycle graph gear graph helm graph ladder graph ladder rung graph Möbius ladder pan graph path graph prism graph star graph sun graph sunlet graph triangular honeycomb rook graph web graph wheel graph

The following table summarizes the recurrence relations for chromatic polynomials for some simple classes of graphs.

The chromatic polynomial of a disconnected graph is the product of the chromatic polynomials of its connected components. The chromatic polynomial of a graph of order has degree , with leading coefficient 1 and constant term 0. Furthermore, the coefficients alternate signs, and the coefficient of the st term is , where is the number of edges. Interestingly, is equal to the number of acyclic orientations of (Stanley 1973).

Except for special cases (such as trees), the calculation of is exponential in the minimum number of edges in and the graph complement (Skiena 1990, p. 211), and calculating the chromatic polynomial of a graph is at least an NP-complete problem (Skiena 1990, pp. 211-212).

Tutte (1970) showed that the chromatic polynomial of a planar triangulation of a sphere possess a root close to (OEIS A104457), where is the golden ratio. More precisely, if is the number of graph vertices of such a graph , then

 (7)

(Tutte 1970, Le Lionnais 1983).

Read (1968) conjectured that, for any chromatic polynomial

 (8)

there does not exist a such that and (Skiena 1990, p. 221).

Chromatic Interval, Chromatic Invariant, Chromatic Number, Chromatic Root, Chromatically Equivalent Graphs, Chromatically Unique Graph, Flow Polynomial, k-Coloring, k-Chromatic Graph, k-Colorable Graph, Q-Chromatic Polynomial, Rank Polynomial, Sigma Polynomial, Tutte Polynomial, Vertex Coloring

## Explore with Wolfram|Alpha

More things to try:

## References

Bari, R. A. "Chromatically Equivalent Graphs." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 186-200, 1974.Berman, G. and Tutte, W. T. "The Golden Root of a Chromatic Polynomial." J. Combin. Th. 6, 301-302, 1969.Biggs, N. L. "Chromatic Polynomials and Spanning Trees." Ch. 14 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 106-111, 1993.Birkhoff, G. D. "A Determinant Formula for the Number of Ways of Coloring a Map." Ann. Math. 14, 42-46, 1912.Birkhoff, G. D. and Lewis, D. C. "Chromatic Polynomials." Trans. Amer. Math. Soc. 60, 355-451, 1946.Chvátal, V. "A Note on Coefficients of Chromatic Polynomials." J. Combin. Th. 9, 95-96, 1970.Dong, F. M., Koh, K. M.; and Teo, K. L. Chromatic Polynomials and Chromaticity of Graphs. Singapore: World Scientific, 2005.Erdős, P. and Hajnal, A. "On Chromatic Numbers of Graphs and Set-Systems." Acta Math. Acad. Sci. Hungar. 17, 61-99, 1966.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 46, 1983.Read, R. C. "An Introduction to Chromatic Polynomials." J. Combin. Th. 4, 52-71, 1968.Saaty, T. L. and Kainen, P. C. "Chromatic Numbers and Chromatic Polynomials." Ch. 6 in The Four-Color Problem: Assaults and Conquest. New York: Dover, pp. 134-163 1986.Skiena, S. "Chromatic Polynomials." §5.5.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 210-212, 1990.Sloane, N. J. A. Sequences A104457 and A140986 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. "Acyclic Orientations of Graphs." Disc. Math. 5, 171-178, 1973.Tutte, W. T. "On Chromatic Polynomials and the Golden Ratio." J. Combin. Th. 9, 289-296, 1970.Yadav, R.; Sehgal, A.; Sehgal, S.; and Malik, A. "The Chromatic Polynomial of Grid Graph ." J. Appl. Math. Comput., 2024.

## Referenced on Wolfram|Alpha

Chromatic Polynomial

## Cite this as:

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