Proof that number of vertex colorings in $k$ colors is a in a graph is a polynomial in terms of k

Question

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?

Answer 1

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)$.

Answer 2

The contraction-deletion formula is the most classical way to see that $P_G(k)$ is a polynomial, but there are more explicit ways. For example, if $\pi_i(G)$ denotes the number of ways to partition $V(G)$ into exactly $i$ independent sets then obviously $$P_G(k)=\sum_i\pi_i(G)k(k-1)\cdots(k-(i-1))$$ because every coloring is obtained by 1) fixing some number $i$ of parts and 2) coloring them with different colors. Of course for any given graph $G$, $\pi_i(G)$ is some constant.