TOPICS
Search

Chromatic Polynomial


The chromatic polynomial pi_G(z) of an undirected graph G, also denoted C(G;z) (Biggs 1973, p. 106) and P(G,x) (Godsil and Royle 2001, p. 358), is a polynomial which encodes the number of distinct ways to color the vertices of G (where colorings are counted as distinct even if they differ only by permutation of colors). For a graph G on n vertices that can be colored in k_0=0 ways with no colors, k_1 way with one color, ..., and k_n ways with n colors, the chromatic polynomial of G is defined as the unique Lagrange interpolating polynomial of degree n through the n+1 points (0,k_0), (1,k_1), ..., (n,k_n). Evaluating the chromatic polynomial in variables z at the points z=1, 2, ..., n then recovers the numbers of 1-, 2-, ..., and n-colorings. In fact, evaluating pi_G(z) at integers k>n still gives the numbers of k-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 z such that pi_G(z)>0 (Skiena 1990, p. 211).

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

 pi_(Q_3)(z)=z^8-12z^7+66z^6-214z^5+441z^4-572z^3+423z^2-133z.
(1)

Evaluating pi_(Q_3)(z) at z=1, 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 g in the variable z 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 G having connected components G_1, G_2, ..., the chromatic polynomial of G itself is given by

 pi_G=pi_(G_1)pi_(G_2)....
(2)

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

 pi=(-1)^(n-c)x^c(1-x)^m.
(3)

For a graph with vertex count n and c connected components, the chromatic polynomial pi(x) is related to the rank polynomial R(x,y) and Tutte polynomial T(x,y) by

pi(x)=x^nR(-x^(-1),-1)
(4)
=(-1)^(n-c)x^cT(1-x,0)
(5)

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

 pi_G(x)=xC_(G^*)^*(x).
(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 P_2 square P_n and grid graph P_2 square P_n are considered by Yadav et al. (2024). The following table summarizes the chromatic polynomials for some simple graphs. Here (z)_n is the falling factorial.

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 n has degree n, with leading coefficient 1 and constant term 0. Furthermore, the coefficients alternate signs, and the coefficient of the (n-1)st term is -m, where m is the number of edges. Interestingly, pi_G(-1) is equal to the number of acyclic orientations of G (Stanley 1973).

Except for special cases (such as trees), the calculation of pi_G(z) is exponential in the minimum number of edges in G and the graph complement G^_ (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 phi^2=phi+1=2.618033... (OEIS A104457), where phi is the golden ratio. More precisely, if n is the number of graph vertices of such a graph G, then

 pi_G(phi^2)<=phi^(5-n)
(7)

(Tutte 1970, Le Lionnais 1983).

Read (1968) conjectured that, for any chromatic polynomial

 pi(z)=c_nz^n+...+c_1z,
(8)

there does not exist a 1<=p<=q<=r<=n such that |c_p|>|c_q| and |c_q|<|c_r| (Skiena 1990, p. 221).


See also

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

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 P_3 square P_n." 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

Subject classifications