If we define $P_G(k)$ to be the number of proper colorings of the graph $G$ in $k$ colors, then it can be shown that $P_G(k)$ is polynomial in terms of k.
I found it easy to show that $P_G(k)$ is of polynomial growth, $\Theta(k^n)$ for a graph with $n$ vertices. The approach was to consider the graphs with minimal and maximal number of proper colorings. The graph with maximal colorings is clearly a collection of $n$ disjoint vertices, call it $N_n$ which has $P_{N_n}(k) = k^n$ colorings. The graph with minimal colorings into k colors is $K_n$ with $P_{K_n}(k) = k(k-1) \cdots (k – n + 1)$ colorings. Then we have for a graph of n vertices $G_n$ that $k^n = P_{N_n}(k) \geq P_{G_n}(k) \geq P_{K_n}(k) = k(k-1) \cdots (k – n + 1)$. Thus $P_{G_n}(k)$ is $\Theta(k^n)$.
It was pointed out to me that having polynomial order of growth does not gaurantee that a function is a polynomial (for example take a polynomial in terms of k and add $(-1)^k$. The book's proof is instead to demonstrate that a modified deletion contraction theorem applies given the standard notation; $G-e$ for the graph with edge $e$ removed and $G/e$ for the graph with the 2 vertices at the ends of the edge collapsed to a single vertex. The formula is constructed by observing these 2 subgraphs $G-e$ and $G+e$ and concluding that they represent a partition into 2 disjoint subsets of the colorings for $G$ s.t. $P_G(k) + P_{G/e}(k) = P_{G-e}(k)$. That is, the number of colorings in the graph where the 2 separated vertices can be either the same color or different colors in a proper coloring is equal to the aum of the number of colorings where they are either the same color or not. Then, the book immediately concludes that $P_G(k)$ is a sum of polynomials and thus itself a polynomial.
Why is this so?
Best Answer
To help explain how the deletion-contraction proof works: it is a strong induction on the number of edges.
(Well, there are a number of ways to set up the induction, but that's one.)
For a graph $G$ with $n$ vertices and no edges, $P_G(k) = k^n$, which is a polynomial, proving the base case.
Now assume that the number of $k$-colorings is a polynomial for all graphs with fewer than $m$ edges. If $G$ is any graph with $n$ vertices and $m$ edges, then $G/e$ and $G-e$ both have at most $m-1$ edges, so by the induction hypothesis, both $P_{G/e}(k)$ and $P_{G-e}(k)$ are polynomials in $k$. Therefore, so is their sum $P_G(k)$.