5.9: The Chromatic Polynomial

Last updated
Save as PDF

Page ID: 7206

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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 \( P_G(k)\) giving the number of ways to color \(G\) with \(k\) colors. Some graphs are easy to do directly.

Example \(\PageIndex{1}\)

If \(G\) is \(K_n\), \( 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\), \( P_G(k)=0\). By Exercise 1.E.9.5 in Section 1.E, we may also write \( P_G(k)=\sum_{i=0}^n s(n,i)k^i\).

Example \(\PageIndex{2}\)

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

Given \(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 \(P_G(k)\) is non-zero. This suggests it will be difficult (that is, time consuming) to compute \(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 \(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). \nonumber\] Since \(G-e\) and \(G/e\) both have fewer edges than \(G\), we can compute \(P_G\) by applying this formula recursively. Ultimately, we need only compute \(P_G\) for graphs with no edges, which is easy, as in Example \(\PageIndex{2}\).

Since \(P_G(k)=k^n\) when \(G\) has no edges, it is then easy to see, and to prove by induction, that \(P_G\) is a polynomial.

Theorem \(\PageIndex{1}\)

For all \(G\) on \(n\) vertices, \(P_G\) is a polynomial of degree \(n\), and \(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 \(\PageIndex{2}\).

Otherwise, by the induction hypothesis, \(P_{G-e}\) is a polynomial of degree \(n\) and \(P_{G/e}\) is a polynomial of degree \(n-1\), so \( P_G=P_{G-e}-P_{G/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.