By submitting the following form, you agree to Club Z!'s Terms of Use and Privacy Policy
By submitting the following form, you agree to Club Z!'s Terms of Use and Privacy Policy
The chromatic polynomial π_G(z) of an undirected graph G, also denoted C(G;z) and P(G, x), 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 π_G(z) at integers k>n still gives the numbers of k-colorings. The chromatic polynomial is called the "chromial" for short by Bari. 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 π_G(z)>0. 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 π_(Q_3)(z) = z^8 - 12z^7 + 66z^6 - 214z^5 + 441z^4 - 572z^3 + 423z^2 - 133z. Evaluating π_(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 π_G = π_(G_1) π_(G_2) .... The chromatic polynomial for a forest on n vertices, m edges, and with c connected components is given by π = (-1)^(n - c) x^c (1 - x)^m. For a graph with vertex count n and c connected components, the chromatic polynomial π(x) is related to the rank polynomial R(x, y) and Tutte polynomial T(x, y) by π(x) | = | x^n R(-x^(-1), -1) | = | (-1)^(n - c) x^c T(1 - x, 0) (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 π_G(x) = x C_(G^*)^*(x). 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 (z)_n is the falling factorial. graph | chromatic 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 graph | z[z - 2 + (3 - 3z + z^2)^n] helm graph | z[(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 n P_2 | z^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_n | z(z - 1)^(n - 1) prism graph Y_n | 1 + [z(z - 3) + 3]^n + z[(1 - z)^n + (3 - z)^n + z - 3] - (1 - z)^n - (3 - z)^n star graph S_n | z(z - 1)^(n - 1) sun graph | (z)_n (z - 2)^n sunlet graph C_n ⊙K_1 | (z - 1)^(2n) - (1 - z)^(n - 1) triangular honeycomb rook graph | product_(k = 1)^n [(z)_k]^n web graph | z[(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_n | z[(z - 2)^(n - 1) - (-1)^n(z - 2)] The following table summarizes the recurrence relations for chromatic polynomials for some simple classes of graphs. graph | order | recurrence antiprism graph | 4 | p_n = (z^2 - 6z + 10) p_(n - 1) + (z - 3)(2z^2 - 9z + 11) p_(n - 2) + (z^2 - 6z + 10)(z - 2)^2 p_(n - 3) - (z - 2)^4 p_(n - 4) barbell graph | 1 | p_n = (z - n + 1)^2 p_(n - 1) book graph S_(n + 1) square P_2 | 1 | p_n = (z^2 - 3z + 3) p_(n - 1) centipede graph | 1 | p_n = (z - 1)^2 p_(n - 1) complete graph K_n | 1 | p_n = (z - n + 1) p_(n - 1) cycle graph C_n | 2 | p_n = (z - 2) p_(n - 1) + (z - 1) p_(n - 2) gear graph | 2 | p_n = (z^2 - 3z + 4) p_(n - 1) - (z^2 - 3z + 3) p_(n - 2) helm graph | 2 | p_n = (z - 3)(z - 1) p_(n - 1) + (z - 2)(z - 1)^2 p_(n - 2) ladder graph P_2 square P_n | 1 | p_n = (z^2 - 3z + 3) p_(n - 1) ladder rung graph n P_2 | 1 | p_n = z(z - 1) p_(n - 1) Möbius ladder | 4 | p_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 graph | 2 | p_n = (z - 1) p_(n - 2) + (z - 2) p_(n - 1) path graph P_n | 1 | p_n = (z - 1) p_(n - 1) prism graph Y_n | 4 | p_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_n | 1 | p_n = (z - 1) p_(n - 1) sunlet graph C_n ⊙K_1 | 2 | p_n = (z - 1)(z - 2) p_(n - 1) + (z - 1)^3 p_(n - 2) web graph | 4 | p_n = p_n = (z^2 - 5z + 8)(z - 1) p_(n - 1) + (z - 2)(2z^2 - 8z + 11)(z - 1)^2 p_(n - 2) + (z^4 - 9z^3 + 29z^2 - 43z + 24)(z - 1)^3 p_(n - 3) - (z - 3)(z^2 - 3z + 3)(z - 1)^5 p_(n - 4) wheel graph W_n | 2 | p_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, π_G(-1) is equal to the number of acyclic orientations of G. Except for special cases (such as trees), the calculation of π_G(z) is exponential in the minimum number of edges in G and the graph complement G^_, and calculating the chromatic polynomial of a graph is at least an NP-complete problem. Tutte showed that the chromatic polynomial of a planar triangulation of a sphere possess a root close to ϕ^2 = ϕ + 1 = 2.61803... (OEIS A104457), where ϕ is the golden ratio. More precisely, if n is the number of graph vertices of such a graph G, then π_G(ϕ^2)<=ϕ^(5 - n) (Tutte 1970, Le Lionnais 1983). Read conjectured that, for any chromatic polynomial π(z) = c_n z^n + ... + c_1 z, there does not exist a 1<=p<=q<=r<=n such that left bracketing bar c_p right bracketing bar > left bracketing bar c_q right bracketing bar and left bracketing bar c_q right bracketing bar < left bracketing bar c_r right bracketing bar .
