Chromic Polynomial
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 .
