
# 5.9: The Chromatic Polynomial

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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

Example 5.9.2 If $G$ has $n$ vertices and no edges, $\ds P_G(k)=k^n$.

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

$\square$

The chromatic polynomial of a graph has a number of interesting and useful properties, some of which are explored in the exercises.

template('TranscludeAutoNum',{'PageNum':'5.9'});