5.9: The Chromatic Polynomial
( \newcommand{\kernel}{\mathrm{null}\,}\)
We now turn to the number of ways to color a graph G with k colors. Of course, if k<χ(G), this is zero. We seek a function PG(k) giving the number of ways to color G with k colors. Some graphs are easy to do directly.
If G is Kn, PG(k)=k(k−1)(k−2)⋯(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, PG(k)=0. By Exercise 1.E.9.5 in Section 1.E, we may also write PG(k)=∑ni=0s(n,i)ki.
If G has n vertices and no edges, PG(k)=kn.
Given PG it is not hard to compute χ(G); for example, we could simply plug in the numbers 1,2,3,… for k until PG(k) is non-zero. This suggests it will be difficult (that is, time consuming) to compute PG. We can provide an easy mechanical procedure for the computation, quite similar to the algorithm we presented for computing χ(G).
Suppose G has edge e={v,w}, and consider PG−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 χ(G) we know this is the number of colorings of G/e. Thus, PG(k)=PG−e(k)−PG/e(k).
Since PG(k)=kn when G has no edges, it is then easy to see, and to prove by induction, that PG is a polynomial.
For all G on n vertices, PG is a polynomial of degree n, and PG 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, PG−e is a polynomial of degree n and PG/e is a polynomial of degree n−1, so PG=PG−e−PG/e is a polynomial of degree n.
The chromatic polynomial of a graph has a number of interesting and useful properties, some of which are explored in the exercises.