Skip to main content
Mathematics LibreTexts

5.9: The Chromatic Polynomial

  • Page ID
  • \( \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}}\)

    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 $\displaystyle 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$, $\displaystyle 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$, $\displaystyle P_G(k)=0$. By exercise 5 in section 1.8, we may also write $\displaystyle P_G(k)=\sum_{i=0}^n s(n,i)k^i$.

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

    Given $\displaystyle 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 $\displaystyle P_G(k)$ is non-zero. This suggests it will be difficult (that is, time consuming) to compute $\displaystyle 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 $\displaystyle 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 $\displaystyle P_G$ by applying this formula recursively. Ultimately, we need only compute $\displaystyle P_G$ for graphs with no edges, which is easy, as in example 5.9.2.

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

    Theorem 5.9.3 For all $G$ on $n$ vertices, $\displaystyle P_G$ is a polynomial of degree $n$, and $\displaystyle P_G$ is called the chromatic polynomial of $G$.

    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, $\displaystyle P_{G-e}$ is a polynomial of degree $n$ and $\displaystyle P_{G/e}$ is a polynomial of degree $n-1$, so $\displaystyle 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.


    Contributors and Attributions