We now turn to the number of ways to color a graph $G$ with $k$ colors. Of course, if $k< \chi(G)$, this is zero. We seek a function $\ds P_G(k)$ giving the number of ways to color $G$ with $k$ colors. Some graphs are easy to do directly.
Example 5.9.1 If $G$ is $K_n$, $\ds P_G(k)=k(k-1)(k-2)\cdots(k-n+1)$, namely, the number of permutations of $k$ things taken $n$ at a time. Vertex 1 may be colored any of the $k$ colors, vertex 2 any of the remaining $k-1$ colors, and so on. Note that when $k< n$, $\ds P_G(k)=0$. By exercise 5 in section 1.8, we may also write $\ds P_G(k)=\sum_{i=0}^n s(n,i)k^i$. $\square$
Given $\ds P_G$ it is not hard to compute $\chi(G)$; for example, we could simply plug in the numbers $1,2,3,\ldots$ for $k$ until $\ds P_G(k)$ is non-zero. This suggests it will be difficult (that is, time consuming) to compute $\ds P_G$. We can provide an easy mechanical procedure for the computation, quite similar to the algorithm we presented for computing $\chi(G)$.
Suppose $G$ has edge $e=\{v,w\}$, and consider $\ds P_{G-e}(k)$, the number of ways to color $G-e$ with $k$ colors. Some of the colorings of $G-e$ are also colorings of $G$, but some are not, namely, those in which $v$ and $w$ have the same color. How many of these are there? From our discussion of the algorithm for $\chi(G)$ we know this is the number of colorings of $G/e$. Thus, $$ P_G(k)=P_{G-e}(k)-P_{G/e}(k). $$ Since $G-e$ and $G/e$ both have fewer edges than $G$, we can compute $\ds P_G$ by applying this formula recursively. Ultimately, we need only compute $\ds P_G$ for graphs with no edges, which is easy, as in example 5.9.2.
Since $\ds P_G(k)=k^n$ when $G$ has no edges, it is then easy to see, and to prove by induction, that $\ds P_G$ is a polynomial.
Theorem 5.9.3 For all $G$ on $n$ vertices, $\ds P_G$ is a polynomial of degree $n$, and $\ds P_G$ is called the chromatic polynomial of $G$.
Proof. The proof is by induction on the number of edges in $G$. When $G$ has no edges, this is example 5.9.2.
Otherwise, by the induction hypothesis, $\ds P_{G-e}$ is a polynomial of degree $n$ and $\ds P_{G/e}$ is a polynomial of degree $n-1$, so $\ds P_G=P_{G-e}-P_{G/e}$ is a polynomial of degree $n$. $\qed$
The chromatic polynomial of a graph has a number of interesting and useful properties, some of which are explored in the exercises.
Exercises 5.9
Ex 5.9.1 Show that the leading coefficient of $P_G$ is 1.
Ex 5.9.2 Suppose that $G$ is not connected and has components $C_1,\ldots,C_k$. Show that $P_G=\prod_{i=1}^k P_{C_i}$.
Ex 5.9.3 Show that the constant term of $P_G(k)$ is 0. Show that the coefficient of $k$ in $P_G(k)$ is non-zero if and only if $G$ is connected.
Ex 5.9.4 Show that the coefficient of $k^{n-1}$ in $P_G$ is $-1$ times the number of edges in $G$.
Ex 5.9.5 Show that $G$ is a tree if and only if $P_G(k)=k(k-1)^{n-1}$.
Ex 5.9.6 Find the chromatic polynomial of $K_n$ with one edge removed.
Ex 5.9.7 Find the chromatic polynomial of the cycle $C_n$, $n\ge 3$.