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.
chromatically equivalent graphs | chromatically unique graph | chromatic invariant | chromatic number | chromatic root | flow polynomial | k-chromatic graph | k-colorable graph | k-coloring | minimum vertex coloring | Q-chromatic polynomial | rank polynomial | sigma polynomial | Tutte polynomial | vertex coloring
