TOPICS
Search

Chromatic Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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.

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.

graphchromatic polynomial
barbell graph((z)_n^2(z-1))/z
book graph S_(n+1) square P_2(z-1)z(z^2-3z+3)^n
centipede graph(z-1)^(2n-1)z
complete graph K_n(z)_n
cycle graph C_n(-1)^n(z-1)+(z-1)^n
gear graphz[z-2+(3-3z+z^2)^n]
helm graphz[(1-z)^n(z-2)+(z-2)^n(z-1)^n]
ladder graph P_2 square P_n(z-1)z(z^2-3z+3)^(n-1)
ladder rung graph nP_2z^n(z-1)^n
Möbius ladder M_n-1+(1-z)^n-(3-z)^n+(-(1-z)^n+(3-z)^n)z+(3+(-3+z)z)^n
pan graph(z-1)^(n+1)+(-1)^n(z-1)^2
path graph P_nz(z-1)^(n-1)
prism graph Y_n1+[z(z-3)+3]^n+z[(1-z)^n+(3-z)^n+z-3]-(1-z)^n-(3-z)^n
star graph S_nz(z-1)^(n-1)
sun graph(z)_n(z-2)^n
sunlet graph C_n circledot K_1(z-1)^(2n)-(1-z)^(n-1)
triangular honeycomb rook graphproduct_(k=1)^(n)[(z)_k]^n
web graphz[(1-z)^n+(3-z)^n+z-3](z-1)^n+(z-1)^n-[-(z-3)(z-1)]^n-[-(z-1)^2]^n+[(z-1)((z-3)z+3)]^n
wheel graph W_nz[(z-2)^(n-1)-(-1)^n(z-2)]

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

graphorderrecurrence
antiprism graph4p_n=(z^2-6z+10)p_(n-1)+(z-3)(2z^2-9z+11)p_(n-2)+(z^2-6z+10)(z-2)^2p_(n-3)-(z-2)^4p_(n-4)
barbell graph1p_n=(z-n+1)^2p_(n-1)
book graph S_(n+1) square P_21p_n=(z^2-3z+3)p_(n-1)
centipede graph1p_n=(z-1)^2p_(n-1)
complete graph K_n1p_n=(z-n+1)p_(n-1)
cycle graph C_n2p_n=(z-2)p_(n-1)+(z-1)p_(n-2)
gear graph2p_n=(z^2-3z+4)p_(n-1)-(z^2-3z+3)p_(n-2)
helm graph2p_n=(z-3)(z-1)p_(n-1)+(z-2)(z-1)^2p_(n-2)
ladder graph P_2 square P_n1p_n=(z^2-3z+3)p_(n-1)
ladder rung graph nP_21p_n=z(z-1)p_(n-1)
Möbius ladder4p_n=(8-5z+z^2)p_(n-1)+(-22+27z-12z^2+2z^3)p_(n-2)+(24-43z+29z^2-9z^3+z^4)p_(n-3)+(-9+21z-18z^2+7z^3-z^4)p_(n-4)
pan graph2p_n=(z-1)p_(n-2)+(z-2)p_(n-1)
path graph P_n1p_n=(z-1)p_(n-1)
prism graph Y_n4p_n=(z^2-5z+8)p_(n-1)+(z-2)(2z^2-8z+11)p_(n-2)+(z^4-9z^3+29z^2-43z+24)p_(n-3)-(z-3)(z-1)(z^2-3z+3)p_(n-4)
star graph S_n1p_n=(z-1)p_(n-1)
sunlet graph C_n circledot K_12p_n=(z-1)(z-2)p_(n-1)+(z-1)^3p_(n-2)
web graph4p_n=p_n=(z^2-5z+8)(z-1)p_(n-1)+(z-2)(2z^2-8z+11)(z-1)^2p_(n-2)+(z^4-9z^3+29z^2-43z+24)(z-1)^3p_(n-3)-(z-3)(z^2-3z+3)(z-1)^5p_(n-4)
wheel graph W_n2p_n=(z-2)p_(n-2)+(z-3)p_(n-1)

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 Invariant, Chromatic Number, 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.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