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.