Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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.

Example 5.9.1

If G is Kn, PG(k)=k(k1)(k2)(kn+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 k1 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.

Example 5.9.2

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 PGe(k), the number of ways to color Ge with k colors. Some of the colorings of Ge 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)=PGe(k)PG/e(k).

Since Ge and G/e both have fewer edges than G, we can compute PG by applying this formula recursively. Ultimately, we need only compute PG for graphs with no edges, which is easy, as in Example 5.9.2.

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.

Theorem 5.9.1

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, PGe is a polynomial of degree n and PG/e is a polynomial of degree n1, so PG=PGePG/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.


This page titled 5.9: The Chromatic Polynomial is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?