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.

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.

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.

graph	order	recurrence
antiprism graph	4
barbell graph	1
book graph	1
centipede graph	1
complete graph	1
cycle graph	2
gear graph	2
helm graph	2
ladder graph	1
ladder rung graph	1
Möbius ladder	4
pan graph	2
path graph	1
prism graph	4
star graph	1
sunlet graph	2
web graph	4
wheel graph	2

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).

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.

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.