Chromatic Polynomial continued

Section 5.4 Chromatic Polynomial continued

It may seem plausible that, if we consider enough cases, the case-by-case method of computing the chromatic polynomial would work for any graph, no matter how complicated. Assuming this, it would follow that the chromatic polynomial \(P_\bfG(k)\) is in fact a polynomial. However, plausibility does not make a proof. In this section we complete the proof elegantly using induction, but first need to introduce the notion of deletion and contraction.

Subsection 5.4.1 Deletion-Contraction

Definition 5.4.1. Deletion.

Let \(\bfG\) be a graph, and let \(e\in\bfG\) be a graph. Then we use \(\bfG\setminus e\) to denote the graph with the same vertex set as \(\bfG\text{,}\) and with all the same edges, except the edge \(e\) deleted.

Definition 5.4.2. Contraction.

Let \(\bfG\) be a simple graph, and let \(e\in \bfG\) be an edge between vertices \(v\) and \(w\text{.}\) Then \(\bfG/e\text{,}\) the graph with \(e\) contracted. More precisely, \(\bfG/e\) is the simple graph with vertices \(V(\bfG/e)=V(\bfG)\setminus \{v,w\}\cup {e}\text{.}\) Two non-\(e\) vertices are adjacent in \(\bfG/e\) if and only if they were adjacent in \(\bfG\text{,}\) and a vertex \(y\) is adjacent to \(e\) in \(\bfG\) if and only if it was adjacent to \(v\) or \(w\) in \(\bfG\text{.}\)

Formally, Definition 5.4.2 seems formidable, but intuitively it is not as bad as the definition looks: we are changing \(\bfG\) by making the whole edge \(e\) into one vertex. This may create multiple edges if a vertex was adjacent to both \(v\) and \(w\text{,}\) and if so we simply remove any duplicate edges.

Lemma 5.4.3. Deletion-Contraction.

Let \(\bfG\) be a simle graph, and let \(e\in \bfG\) be any edge. Then we have:

\begin{equation*} P_\bfG(k)=P_{\bfG\setminus e}(k)-P_{\bfG/e}(k) \end{equation*}

Proof.

Since \(\bfG\) and \(\bfG\setminus e\) have the same vertex, it is not too difficult to compare their colourings. Any valid colouring of \(\bfG\) will give a colouring of \(\bfG\setminus e\text{,}\) but not every colouring of \(\bfG\setminus e\) arises this way -- in \(\bfG\text{,}\) colourings require that \(v\) and \(w\text{,}\) the two endpoints of \(e\text{,}\) have different colours, but there is no such requirement for \(\bfG\setminus e\text{.}\) So, we want to count the colourings of \(\bfG\setminus e\) where \(v,w\) have the same colour. But these are just the colourings of \(\bfG/e\text{:}\) given a colouring of \(\bfG/e\)m we can get a colouring of \(\bfG\) by giving most vertices the same colour, and giving both \(v,w\) whatever colour \(e\) was. By definition, we see that \(v\) and \(w\) will have the same colour in this colouring; and given any colouring of \(\bfG\setminus e\) where \(v,w\) have the same colour we can get a colouring of \(\bfG/e\) by colouring \(e\) the colour that \(v,w\) were.

Example 5.4.4. Chromatic polynomial of \(C_4\text{,}\) again.

Let us compute \(P_{C_4}(k)\) a different way as an illustration of how deletion-contraction works. No matter which edge of \(C_4\) we pick, \(C_4\setminus e\) will be the path graph \(P_4\text{,}\) which is a tree, and hence we know has chromatic polynomial \(k(k-1)^3\text{.}\) Similarly, we have that \(C_4/e=C_3\text{,}\) and we know \(P_{C_3}(k)=k(k-1)(k-2)\text{.}\) Hence we have:

\begin{align*} P_{C_4}(k) \amp = P_{C_4\setminus e}(k)-P_{C_4/e}(k) \\ \amp = P_{P_4}(k)-P_{C_3}(k) \\ \amp = k(k-1)^3 - k(k-1)(k-2) \\ \amp = k(k-1)\left( (k-1)^2-(k-2)\right) = k(k-1)(k^2-3k3+3) \end{align*}

Since \(\bfG\setminus e\) and \(\bfG/e\) both have fewer edges than \(\bfG\text{,}\) it follows that we can repeatedly apply Deletion-Contraction to \(\bfG\) until we have no edges left at all, and hence that Deletion-Contraction can compute the chromatic polynomial of any graph. In practice, this can be quite a complicated and formidable way to compute, but in the next section we show that this method can elegantly prove the chromatic polynomial is always a polynomial, and in some cases give nice formulas for this polynomial.

Subsection 5.4.2 Chromatic polynomial is a polynomial

We first prove that the chromatic polynomial is actually a polynomial, but iterative use of deletion-contraction.

Theorem 5.4.5.

Let \(\bfG\) be a simple graph with \(n\) vertices and \(\) edges. Then \(P_\bfG(k)\) is a polynomial of degree \(n\) in \(k\text{,}\) and moreover:

\begin{equation*} P_\bfG(k)=k^n-mk^{n-1}+\text{lower order terms} \end{equation*}

Proof.

The proof follows from induction on \(m\text{,}\) the number of edges, using deletion-contraction for the inductive step.

As a base case, we take \(m=0\text{.}\) Then if \(\bfG\) has \(n\) vertices it must be the empty graph \(E_n\text{.}\) We have seen that \(P_{E_n}(k)=k^n\text{,}\) which indeed has the correct form needed for the theorem.

Now, for the inductive step, we assume that for any graph \(H\) with \(\ell\lt m\) edges and \(n\) vertices, we have \(P_{H}(k)=k^n-\ell k^{n-1}+\text{lower order terms}\text{.}\)

Now let \(\bfG\) be any graph with \(m\) edges. We can assume \(m\gt 0\text{,}\) as the case where \(m=0\) is the base case; this means that \(\bfG\) has at least one edge \(e\text{.}\) We apply deletion-contraction to the edge \(e\text{.}\)

If we delete \(e\text{,}\) the resulting graph \(\bfG\setminus e\) still has \(n\) vertices, but it now has \(m-1\) edges. Since this is less than \(m\text{,}\) we know by the inductive hypothesis that

\begin{equation*} P_{\bfG\setminus e}(k)=k^n-(m-1)k^{n-1}+\text{lower order terms} \end{equation*}

If we contract \(e\text{,}\) the resulting graph \(\bfG/e\) has \(n-1\) vertices, and we don't know exactly how many edges it has (contracting it may create multiple edges that need to be deleted), but it has at most \(m-1\) edges, and so by the inductive hypothesis we know that

\begin{equation*} P_{\bfG/e}(k)=k^{n-1}+\text{lower order terms} \end{equation*}

Thus, applying deletion-contraction we have:

\begin{align*} P_\bfG(k) \amp = P_{\bfG\setminus e}(k)-P_{\bfG/e}(k) \\ \amp = k^n-(m-1)k^{n-1}+\text{lower order terms} - \left(k^{n-1}+\text{lower order terms} \right)\\ \amp = k^n-mk^{n-1}+\text{lower order terms} \end{align*}

which is what we needed to show to finish the inductive step.

We end by showing that sometimes the inductive method of iteratively using deletion-contraction can compute explicit formulas for the chromatic polynomials of an infinite family of graphs.

Lemma 5.4.6. Chromatic polynomial of \(C_n\).

Let \(C_n\) be the cycle graph on \(n\) vertices. Then:

\begin{equation*} P_{C_n}(k) = (k-1)^n+(-1)^n(k-1) \end{equation*}

Proof.

We will induct on \(n\text{.}\) As a base case, when \(n=3\text{,}\) we have:

\begin{align*} (k-1)^3+(-1)^3(k-1)\amp =k^3-3k^2+3k-1-(k-1)\\ \amp=k^3-3k^2+2k\\ \amp =k(k-1)(k-2) \\ \amp=P_{C_3}(k) \end{align*}

For the inductive step, we assume that the proposition holds for \(n-1\) and want to prove that it holds for \(n\text{.}\) We will compute \(P_{C_n}(k)\) by deletion-contraction. If we delete any edge of \(C_n\text{,}\) we get the path graph \(P_n\text{,}\) and we know

\begin{gather*} \end{gather*}

If we contract any edge of \(C_n\text{,}\) we get \(C_{n-1}\text{,}\) and we know by the inductive hypothesis that

\begin{gather*} \end{gather*}

Plugging these into deletion-contraction gives:

\begin{align*} P_{C_n}(k) \amp = P_{C_n \setminus e}(k)-P_{C_n/e}(k) \\ \amp = P_{P_n}(k)-P_{C_{n-1}}(k) \\ \amp = k(k-1)^{n-1} - \left((k-1)^{n-1}+(-1)^{n-1}(k-1) \right)\\ \amp = (k-1)^{n-1}(k-1) - (-1)^{n-1}(k-1) \\ \amp = (k-1)^n+(-1)^n(k-1) \end{align*}

as was desired.