Graph Colorings | An Introduction to Algebraic Graph Theory

A university is organizing a conference on undergraduate research that will contain \(n\) student presentations. Prior to the conference, the participants selected which presentations they plan to attend and the conference organizers would like to schedule the presentations (each of the same time length) so that participants can attend all the presentations they selected and the presentation they will deliver. The university has many rooms to use for the conference and can therefore schedule presentations in parallel. The organizers would like to minimize the time for all presentations to complete. This scheduling problem can be described using a graph as follows. Let \(v_1, v_2, \ldots, v_n\) be the presentations. The presentations \(v_i\) and \(v_j\) are adjacent if there is a participant who will attend both \(v_i\) and \(v_j\). Let \(\{1,2,\ldots,k\}\) be the number of time slots during which parallel presentations will be held. The scheduling problem is then to assign to each presentation a time slot \(s\in\{1,2,\ldots,k\}\) so that adjacent presentations receive a distinct time slot.

The basics

We begin with the definition of a graph coloring.

Let \(G=(V,E)\) be a graph and let \(k\) be a positive integer. A \(k\)-coloring of the graph \(G\) is a function \(f:V\rightarrow \{1,2,\ldots, k\}\) such that if \(v_i\) and \(v_j\) are adjacent then \(f(v_i)\neq f(v_j)\). If \(G\) has a \(k\)-coloring then we say that \(G\) is \(k\)-colorable. The set of numbers \(\{1,2,\ldots,k\}\) are called the colors of the coloring \(f\).

For each graph, find a coloring.

\(G=C_4\vee K_1\)
\(G=P_5\)
\(G\) is two \(K_3\)'s connected by a bridge
\(G=E_4\)
\(G=K_4\)

Suppose that \(f:V(G)\rightarrow\set{1,\ldots,k}\) is a \(k\)-coloring of \(G\). Let \(C_i = \{ v\in V\;|\; f(v) = i\}\) and assume \(C_i\neq\emptyset\) for each \(i=1,2,\ldots,k\). By definition, \(C_i\) consists of vertices that are colored with the same color \(i\) and we call \(C_i\) a color class induced by \(f\). By definition of a coloring, any two vertices in \(C_i\) are not adjacent. In general, a non-empty subset \(C\subset V(G)\) is called an independent set if no two vertices in \(C\) are adjacent. Hence, if \(C_1, C_2, \ldots, C_k\) are the color classes induced by \(f\) then each non-empty color class \(C_i\) is an independent set. Moreover, since each vertex receives a color, \(\{C_1,C_2,\ldots, C_k\}\) is a partition of the vertex set \(V(G)\).

Obtain a coloring of the given graph and list the color classes.\\

If \(G\) is \(k\)-colorable then it is also \(k'\)-colorable for any \(k' \geq k\) (prove this!). Given a graph \(G\), it is natural then to ask for the smallest integer \(k\geq 1\) such that \(G\) is \(k\)-colorable. This number is given a special name.

The chromatic number of \(G\), denoted by \(\chi(G)\), is the smallest integer \(k\) such that \(G\) is \(k\)-colorable.

It is clear that if \(G\) has at least one edge then \(\chi(G)\geq 2\).

Prove that \[ \chi(C_n) = \begin{cases} 2, & \text{if \(n\) is even},\\ 3, & \text{if \(n\) is odd.}\end{cases} \] Solution: Label the vertices of \(C_n\) so that \(E(C_n) = \{v_1v_2, v_2v_3,\) \(\ldots, v_{n-1}v_n, v_nv_1\}\) and recall that we must have \(n\geq 3\). Suppose that \(n\geq 3\) is odd. Define \(f:V\rightarrow\set{1,2,3}\) as follows: let \(f(v_i) = 1\) if \(i \lt n\) is odd, let \(f(v_j) = 2\) if \(j\) is even, and let \(f(v_n) = 3\). Then \(f:V(C_n)\rightarrow \{1,2,3\}\) is a coloring. Suppose by contradiction that \(\tilde{f}:V\rightarrow\set{1,2}\) is a coloring of \(C_n\). We can assume without loss of generality that \(\tilde{f}(v_1) = 1\). Then \(\tilde{f}(v_j) = 2\) if \(j\) is even. Since \(v_n\sim v_{n-1}\), and \(n-1\) is even, we must have \(\tilde{f}(v_n)=1\). However, \(v_n \sim v_1\) and thus \(\tilde{f}\) is not a coloring. Hence, \(\chi(C_n) = 3\) if \(n\) is odd. Now suppose that \(n\geq 3\) is even. Then \(f:V\rightarrow\set{1,2}\) define by \(f(v_i) = 1\) if \(i\) is odd and \(f(v_j) = 2\) if \(j\) is even is a coloring. Hence, \(\chi(C_n)\leq 2\) and thus \(\chi(G) = 2\) since \(C_n\) is not the empty graph.

Compute the chromatic numbers of the wheels \(W_5 = C_5\vee K_1\) and \(W_6=C_6\vee K_1\). What about \(W_n = C_n \vee K_1\) for any \(n\geq 3\)?

Prove that \(\chi(G_1 \oplus G_2\oplus \cdots \oplus G_r) = \max\{\chi(G_1),\chi(G_2),\ldots,\chi(G_r)\}\).

Prove that if \(\chi(G) = n\) then \(G=K_n\).

Bounds on the chromatic number

Given a graph \(G\) with \(n\) vertices, we may color each vertex with a distinct color and obtain a \(n\)-coloring. This shows that \(\chi(G)\leq n\). It is clear that a coloring of \(K_n\) must have at least \(n\) colors and thus \(\chi(K_n) = n\). On the other hand, the empty graph \(E_n\) can be colored (properly) with only one color and thus \(\chi(E_n)=1\). However, if \(G\) has at least one edge then \(2\leq \chi(G)\). We therefore have the following.

For any graph \(G\) not equal to \(K_n\) or \(E_n\), we have that \(2\leq \chi(G)\leq n-1\).

A lower bound on \(\chi(G)\) is obtained through the notion of a clique and clique number of a graph.

A subset \(W\subset V(G)\) is called a clique if all vertices in \(W\) are mutually adjacent. In other words, \(W\) is a clique if and only if \(G[W]\) is a complete graph. The clique number of a graph \(G\) is the cardinality of a largest clique in \(G\), and is denoted by \(\omega(G)\).

What is the clique number of a cycle? More generally, of a bipartite graph?

If \(W\) is a clique in \(G\) then any coloring of \(G\) must assign distinct colors to vertices in \(W\), and thus any coloring of \(G\) must contain at least \(\omega(G)\) colors. We therefore obtain the following.

For any graph \(G\) we have \(\omega(G) \leq \chi(G)\).

As an example of a graph for which \(\omega(G) \lt \chi(G)\), take a cycle \(C_n\) of odd length. In Example 3.3 we showed that \(\chi(C_n) = 3\) if \(n\) is odd; on the other hand \(\omega(C_n) = 2\) for all \(n\geq 3\).

Recall that \(C\subset V(G)\) is an independent set if no two vertices in \(C\) are adjacent. The independence number of \(G\), denoted by \(\alpha(G)\), is the cardinality of a largest independent set in \(G\).

Prove that \(\omega(\overline{G}) = \alpha(G)\).\\ Solution: Let \(C\) be an independent set with cardinality \(\alpha(G)\). Then \(C\) is a clique in \(\overline{G}\) and therefore \(\alpha(G)\leq \omega(\overline{G})\). Conversely, suppose that \(W\) is a largest clique in \(\overline{G}\). Then \(W\) is an independent in \(G\). Therefore, \(\omega(\overline{G}) \leq \alpha(G)\). This proves the claim. \(\square\)

Suppose that \(\set{C_1,C_2,\ldots,C_k}\) are the color classes of a \(k\)-coloring in \(G\). Then \(|C_i| \leq \alpha(G)\) for all \(i=1,2,\ldots,k\). It follows that \[ n = \sum_{i=1}^k |C_i| \leq \sum_{i=1}^k \alpha(G) = k \alpha(G). \] We may take \(k=\chi(G)\) and therefore \[ n \leq \chi(G)\alpha(G). \] Suppose now that \(C\) is a largest independent set in \(V(G)\), and thus \(|C|=\alpha(G)\). Color all vertices in \(C\) with color \(1\). The remaining \(n-\alpha(G)\) vertices may be colored with distinct colors, say \(\set{2,\ldots,n-\alpha(G)}\). This produces a \(k=n-\alpha(G)+1\) coloring of \(G\). Therefore, \[ \chi(G) \leq n - \alpha(G) + 1. \] To summarize:

For every graph \(G\) it holds that \[ \frac{n}{\alpha(G)} \leq \chi(G) \leq n - \alpha(G) + 1 \]

We now describe a greedy algorithm that always produces a coloring. Let \(v_1, v_2, \ldots, v_n\) be an ordering of the vertices of \(G\). For each vertex \(v_i\), let \(\mu_i\geq 0\) be the number of vertices adjacent to \(v_i\) that are lower in the order, that is, \(\mu_i = |\{v_j \, |\, j \lt i, \; v_iv_j \in E(G)\}|\). It is clear that \(\mu_i \leq \Delta(G)\) and thus \(\mu = \max_{1\leq i\leq n} \mu_i \leq \Delta(G)\). Hence, for each vertex \(v_i\), the number of neighbors of \(v_i\) that are lower in the order is at most \(\mu\geq 0\).

With the notation above, it holds that \(\chi(G) \leq \mu +1\). In particular, \(\chi(G) \leq \Delta(G) + 1\).

Consider the set of colors \(\set{1,\ldots,\mu+1}\). Color \(v_1\) with the color \(1\). Suppose that \(v_1,\ldots,v_i\) have been colored so that no adjacent vertices received the same color. Now consider \(v_{i+1}\). The number of vertices adjacent to \(v_{i+1}\) that have already been colored is at most \(\mu\). Hence, we can color \(v_{i+1}\) with \(\mu+1\) or with a lower color and thereby produce a proper coloring of the vertices \(v_1,\ldots,v_{i+1}\). By induction, this proves that \(G\) can be colored with at most \(\mu+1\) colors.

The following example shows that the number of colors needed in the greedy algorithm depends on the chosen ordering of the vertices.

Consider the cycle \(C_6\) with vertices labelled in two different ways as shown below. Apply the greedy coloring algorithm in each case.

Verify that if \(G\) is a complete graph or a cycle with an odd number vertices then the inequality in Theorem 3.2.5 is an equality when \(\mu=\Delta(G)\).

It turns out that complete graphs and cycles of odd length are the only graphs for which equality holds in Theorem 3.2.5. This is known as Brook's theorem.

If \(G\) is a connected graph that is neither a complete graph or an odd cycle then \(\chi(G)\leq \Delta(G)\).

In this exercise, we are going to prove that there is a labelling of the vertices of \(G\) so that the greedy algorithm uses exactly \(k=\chi(G)\) colors. Suppose that \(C_1, C_2, \ldots, C_k\) are the color classes of some chromatic coloring of \(G\) and let \(m_i = |C_i|\) for \(i=1,2\ldots, k\). Label the vertices of \(G\) so that the first \(m_1\) vertices are in \(C_1\), the next \(m_2\) vertices are in \(C_2\), and repeatedly until the last \(m_k\) vertices are in \(C_k\). Explicitly, \(C_1 = \{v_1, v_2, \ldots, v_{m_1}\}\), \(C_2 = \{v_{m_1 + 1}, v_{m_1+2}, \ldots, v_{m_1 + m_2}\}\), until finally \(C_k = \{v_{n-m_k+1}, v_{n-m_k+2}, \ldots, v_n\}\). Since \(C_1\) is an independent set, we can color all vertices in \(C_1\) with color 1. Now consider the vertices in \(C_2\). If \(v\in C_2\) is adjacent to a vertex in \(C_1\) then we must color \(v\) with color 2, otherwise we can color \(v\) with color 1. Since \(C_2\) is an independent set, after this re-coloring the vertices in \(C_2\) receiving the same color are not adjacent. Now consider the vertices in \(C_3\). For \(v\in C_3\), we can choose one of the colors \(\{1,2,3\}\) to color \(v\); for example, if \(v\) is not adjacent to any vertex in \(C_1\) then color \(v\) with color 1, if \(v\) is not adjacent to any vertex in \(C_2\) then color \(v\) with color 2; otherwise we need to color \(v\) with 3. Since \(C_3\) is an independent set, the vertices in \(C_3\) receiving the same color are not adjacent. By induction, suppose that we have colored all vertices up to and including \(C_{j-1}\). Any vertex in \(v\in C_{j}\) is adjacent to at most \(j-1\) colored vertices, all of which have been colored with one of \(1,2,\ldots, j-1\). Hence, to color \(v\in C_{j}\) we can choose the smallest available color from \(\{1,2,\ldots, j\}\). This proves that the greedy algorithm uses at most \(k\) colors. Since \(k=\chi(G)\), the greedy algorithm uses exactly \(k\) colors. We note that, in general, the new coloring will produce distinct color classes. As an example, consider the chromatic 4-coloring of the graph \(G\) in Figure 3.1. The coloring is indeed chromatic since \(\chi(G) = \omega(G) = 4\). The color classes are \(C_1=\{v_1, v_2, v_3\}\), \(C_2=\set{v_4,v_5,v_6}\), \(C_3=\set{v_7,v_8}\), and \(C_4=\set{v_9, v_{10}}\). Starting with the labelling shown in Figure 3.1, and performing the greedy algorithm, we obtain a new coloring with color classes \(\widetilde{C}_1=\set{v_1,v_2,v_3}\), \(\widetilde{C}_2=\set{v_4,v_5,v_6,v_7}\), \(\widetilde{C}_3=\set{v_8,v_9}\), and \(\widetilde{C}_4=\set{v_{10}}\). Note that this produces a distinct chromatic coloring of \(G\).

figures/greedy-coloring-algorithm-2.svg — A labelling of \(G\) from a chromatic coloring for which the greedy algorithm produces a (new) chromatic coloring

Let \(G\) be a \(k\)-chromatic graph, that is, \(k=\chi(G)\). Show that in every \(k\)-coloring of \(G\), there exists at least one vertex in each color class that is adjacent to at least one vertex in each of the other color classes. Deduce that \(G\) has at least \(k\) vertices with degree at least \(k-1\).
Solution: Let \(C_1, C_2, \ldots, C_k\) be the color classes of a \(k\)-chromatic coloring of \(G\). Suppose by contradiction that some color class \(C_i\) contains no vertex that is adjacent to at least one vertex in each of the other classes. We can assume without loss of generality that this color class is \(C_k\). We will re-color the vertices in \(C_k\) to produce a \((k-1)\) coloring as follows. Since each \(v\in C_k\) is non-adjacent to at least one of the other color classes, there is a color available in \(\{1,2,\ldots, k-1\}\) to re-color \(v\in C_k\). Hence, this re-coloring of \(G\) produces a \((k-1)\) coloring which is a contradiction since \(k=\chi(G)\). Thus, every color class has at least one vertex adjacent to the other color classes. This clearly implies the existence of \(k\) vertices with degree at least \(k-1\).\(\square\)

The following theorem gives in many cases a better upper bound than Brook's theorem \cite{HW:67}.

Let \(G\) be a graph and let \(\lambda_{\max}\) denote the largest eigenvalue of the adjacency matrix of \(G\). Then \(\chi(G) \leq 1 + \lambda_{\max}\). Moreover, equality holds if and only if \(G\) is a complete graph or an odd cycle.

If \(G\) has a large clique then \(\chi(G)\) is also large since \(\omega(G)\leq \chi(G)\). In every non-trivial clique (i.e., a clique containing at least 3 vertices), there is a triangle. Hence, if \(G\) has no triangles then \(\omega(G)=2\), and thus it is reasonable to investigate whether graphs with no triangles have small \(\chi(G)\). Surprisingly, this is not the case.

For any \(k\geq 1\), there exists a \(k\)-chromatic graph with no triangles.

The proof is by induction on \(k\geq 1\). If \(k=1\) then \(K_1\) is a triangle-free \(k\)-chromatic graph and when \(k=2\) then \(K_2\) is a triangle-free \(k\)-chromatic graph. Assume that \(G_k\) is a triangle-free \(k\) chromatic graph and let \(v_1, v_2,\) \(\ldots, v_n\) be the vertices of \(G_k\). Add new vertices \(u_1, u_2, \ldots, u_n\) and \(v\), and connect \(u_i\) to \(v\) and also to the neighbors of \(v_i\), for \(i=1,2,\ldots, n\). Denote the resulting graph by \(G_{k+1}\). Any \(k\)-coloring of \(G_k\) can be extended to a \((k+1)\)-coloring of \(G_{k+1}\) by coloring \(u_{i}\) with the same color as \(v_i\), for \(i=1,2,\ldots,n\), and coloring \(v\) with \(k+1\). Hence, \(\chi(G_{k+1}) \leq k+1\). Assume that \(G_{k+1}\) is \(k\)-colorable and suppose without loss of generality that \(v\) is colored with \(k\). Then no vertex \(u_i\) is colored with \(k\). If \(v_j\) is colored with \(k\) then recolor it with the same color as \(u_j\). Since no vertex \(u_i\) is colored with \(k\), this produces a \((k-1)\)-coloring of \(G_k\), which is a contradiction. Hence, \(\chi(G_{k+1}) = k+1\). We now prove \(G_{k+1}\) is triangle-free. Since \(\{u_1, u_2, \ldots, u_n\}\) is an independent set in \(G_{k+1}\) and no vertex \(v_i\) is adjacent to \(v\), any triangle in \(G_{k+1}\) (if any) must consist of two vertices \(v_i\) and \(v_j\) and one vertex \(u_k\). But if \(v_i, v_j, u_k\) are the vertices of a triangle in \(G_{k+1}\) then \(v_i\sim u_k\) and \(v_j \sim u_k\) implies that \(v_i \sim v_k\) and \(v_j \sim v_k\) and thus \(v_i, v_j, v_k\) are the vertices of a triangle in \(G_k\), which is a contradiction. Hence, \(G_{k+1}\) is triangle-free and the proof is complete.

The punchline of Theorem 3.2.8 is that the chromatic number can get arbitrarily high even if we limit in the strongest way the size of the largest clique.

The Chromatic Polynomial

For each non-negative integer \(k\geq 0\) let \(P_G(k)\) be the number of distinct \(k\)-colorings of \(G\). The function \(P_G\) was introduced by George Birkhoff (1912) in his quest to prove the Four Color Theorem for planar graphs. Let us clarify what we mean by ``distinct colorings''. Recall that a \(k\)-coloring of \(G\) is a function \(f:V(G)\rightarrow\{1,\ldots,k\}\). Hence, \(f_1\) and \(f_2\) are two distinct \(k\)-colorings if \(f_1(v) \neq f_2(v)\) for at least one vertex \(v\in V(G)\), that is, at least one vertex of \(G\) is colored differently in the colorings \(f_1\) and \(f_2\). Before we proceed we note that if \(G\) has at least one vertex then \(P_G(0)=0\) since there is no way to color the vertices of a graph with \(k=0\) colors.

For each graph shown below, produce two distinct colorings using \(k=2\) and \(k=3\) colorings, respectively.

Let us prove that \(P_G\) is an invariant.

If \(G_1\) and \(G_2\) are isomorphic graphs then \(P_{G_1}(k) = P_{G_2}(k)\) for every integer \(k\geq 0\).

This is left as an important exercise.

Consider the empty graph \(G=E_n\) and let \(k\geq 1\). We can color vertex \(v_1\) with any of the colors \(\{1,2,\ldots, k\}\), we can color \(v_2\) with any of the colors \(\{1,2,\ldots, k\}\), etc. Any such \(k\)-coloring is and thus the number of \(k\)-colorings of \(G=E_n\) is \(P_G(k) = k^n\). Now consider the other extreme, i.e., consider \(G=K_n\). If \(k \lt n\) then there are no \(k\)-colorings of \(G\), and thus \(P_G(k) = 0\) for \(k \lt n\). Suppose then that \(k\geq n\). We start by coloring \(v_1\) by choosing any of the \(k\) colors. Then we have \((k-1)\) color choices to color \(v_2\), then \((k-2)\) color choices to color \(v_3\), and inductively we have \((k-(n-1))\) color choices for \(v_n\). Hence, the number of \(k\)-colorings of \(K_n\) is \[ P_{K_n}(k) = k (k-1)(k-2)\ldots (k-(n-1)). \] Notice that our formula for \(P_{K_n}(k)\) is a polynomial function in \(k\), as was for \(P_{E_n}(k)=k^n\). Now, the polynomial expression we obtained for \(P_{K_n}(k)\) has the property that \(P_{k_n}(x) = 0\) if \(x\in\{0,1,\ldots, n-1\}\) which is exactly the statement that there are no colorings of \(K_n\) using less than \(n\) colors. If for example \(k=n\) then we obtain \[ P_{K_n}(n) = n (n-1) (n-2) \ldots 1 = n! \]

For any graph \(G\) it holds that \[ \chi(G) = \min\{ k\in\{0,1,\ldots,n\} \;|\; P_G(k) \gt 0\}. \] Equivalently, \(P_G(k) \gt 0\) if and only if \(k\geq \chi(G)\).

If \(P_G(k) \gt 0\) then there is a \(k\)-coloring of \(G\) and thus by definition of \(\chi(G)\) we have \(\chi(G)\leq k\). If on the other hand \(k\geq \chi(G)\) then since we can color \(G\) with \(\chi(G)\) colors then we can certainly color \(G\) with \(k\) colors and thus \(P_G(k) \gt 0\). By definition of \(\chi(G)\), if \(k \lt \chi(G)\) then there are no \(k\)-colorings of \(G\) and thus \(P_G(k) = 0\).

Directly finding \(P_G(k)\) for anything other than \(G=K_n\) or \(G=E_n\) as we did above quickly becomes a non-trivial exercise. There is, as we describe below, a recursive reductive approach to compute \(P_G(k)\). Before we state the relevant theorem, we need some notation. If \(e\) is an edge recall that \(G-e\) is the graph obtained by deleting the edge \(e\). We define the graph \(G/e\) as the graph obtained by removing the edge \(e\), identifying the end-vertices of \(e\), and eliminating any multiple edges.

Draw any graph \(G\), pick an edge \(e\), and draw \(G/e\).

For any graph \(G\) and \(e\in E(G)\) it holds that \[ P_G(k) = P_{G-e}(k) - P_{G/e}(k). \]

We consider the number of colorings of \(G-e\). We partition the of colorings of \(G-e\) into two types. The first are the colorings in which the end-vertices of \(e\) are colored differently. Each such coloring is clearly a coloring of \(G\). Hence, there are \(P_G(k)\) such colorings. The second are the colorings in which the end-vertices of \(e\) are colored the same. Each such coloring is clearly a coloring of \(G/e\). The number of such colorings is \(P_{G/e}(k)\). Hence, the total number of colorings of \(G-e\) is \[ P_{G-e}(k) = P_G(k) + P_{G/e}(k) \] and the claim follows.

The upshot of the reduction formula \[ P_G(k) = P_{G-e}(k) - P_{G/e}(k) \] is that \(P_{G/e}\) has one less vertex and edge than \(G\) and \(G-e\) has one less edge and might have more components than \(G\). Regarding the latter case, the following will be useful.

If \(G=G_1\oplus G_2\) then \[ P_{G}(k) = P_{G_1}(k) P_{G_2}(k). \]

By definition, \(V(G_1\oplus G_2) = V(G_1) \cup V(G_2)\). The number of ways to properly color the vertices in \(V(G_1)\) is \(P_{G_1}(k)\) and the number of ways to properly color the vertices in \(V(G_2)\) is \(P_{G_2}(k)\). Since both colorings can be done independently, the result follows.

Find the chromatic polynomials of the graphs shown in Figure 3.2.

figures/find-chromatic-polynomial.svg — Graphs for Example 3.16

We now prove some basic properties of the function \(P_G(k)\).

Let \(G\) be a graph of order \(n\). The function \(P_G(k)\) is a monic polynomial of degree \(n\) with integer coefficients.

We induct over the number of edges. If \(G\) has no edges then \(G=E_n\) and we showed above that \(P_G(k) = k^n\). This proves the base case. Now suppose the claim holds for all graphs with no more than \(m\geq 0\) edges and let \(G\) be a graph with \(m+1\) edges and \(n\) vertices. Pick any edge \(e \in E(G)\). By the chromatic reduction theorem, \(P_G(k) = P_{G-e}(k) - P_{G/e}(k)\). The graph \(G-e\) contains \(m\) edges and \(n\) vertices, and \(G/e\) has \(n-1\) vertices and no more than \(m\) edges. By induction, \(P_{G-e}(k)\) is a monic polynomial of degree \(n\) with integer coefficients and \(P_{G/e}(k)\) is a monic polynomial of degree \(n-1\) with integer coefficients. Hence, \(P_G(k)\) is a monic polynomial of degree \(n\) with integer coefficients.

Based on the result of Theorem 3.3.5, we call \(P_G(k)\) the chromatic polynomial of the graph \(G\).

For any graph \(G\), the chromatic polynomial \(P_G(k)\) can be written in the form \[ P_G(k) = k^n - a_1 k^{n-1} + a_2 k^{n-2} - a_3 k^{n-3} + \cdots + (-1)^{n-1} a_{n-1} k \] where \(a_j \geq 0\).

We induct over the number of edges. If \(G\) is the empty graph then \(P_G(k) = k^n\) clearly satisfies the claim. Suppose the claim is true for all graphs with no more than \(m\geq 0\) edges and let \(G\) be a graph with \(m+1\) edges and \(n\) vertices. By induction, we may write that \[ P_{G-e}(k) = k^n + \sum_{j=1}^{n-1} (-1)^j a_j k^{n-j} \] where \(a_j \geq 0\) and \[ P_{G/e}(k)= k^{n-1} + \sum_{j=2}^{n-1} (-1)^{j+1} b_j k^{n-j} \] where \(b_j \geq 0\). Then \begin{align*} P_G(k) &= P_{G-e}(k) - P_{G/e}(k)\\[2ex] &= k^n + \sum_{j=1}^{n-1} (-1)^j a_j k^{n-j} - k^{n-1} + \sum_{j=2}^{n-1} (-1)^j b_j x^{n-j}\\[2ex] &= k^n - (a_1 + 1)k^{n-1} + \sum_{j=2}^{n-1} (-1)^j (a_j + b_j) k^{n-j} \end{align*} and this proves the claim.

We now prove an important property about the coefficients of \(P_G(k)\) when \(G\) is connected but first we need the following lemma.

Suppose that \(G\) contains \(n\geq 2\) vertices. If \(G\) is connected then \(G/e\) is connected for any \(e\in E(G)\).

The proof is left as an exercise.

If \(G\) is connected then the coefficients of \(k, k^2, \ldots, k^n\) in \(P_G(k)\) are all non-zero.

The proof is by induction on the number of edges. If \(m=1\) then \(G=P_2\) and it is not hard to see that \(P_G(k) = k(k-1) = k^2 - k\). Hence, the claim holds for \(m=1\). Assume that the claim holds for all connected graphs with at most \(m\geq 1\) edges and let \(G\) be a graph with \(m+1\) edges and \(n\) vertices. If \(e\in E(G)\) then \(G/e\) has at most \(m\) edges and thus by induction the coefficients of \(k, k^2, \ldots, k^{n-2}\) in \(P_{G/e}(k)\) are non-zero. Using the notation in the proof of Lemma 3.3.6, we may write that \(P_{G/e}(k) = k^{n-1} + \sum_{j=2}^{n-1} (-1)^{j+1} b_j k^{n-j}\) where \(b_j \gt 0\). Again, using the notation in the proof of Lemma 3.3.6 we may write \[ P_G(k) = k^n - (a_1 + 1)k^{n-1} + \sum_{j=2}^{n-1} (-1)^j (a_j + b_j) k^{n-j} \] where \(a_j\geq 0\). This proves that the coefficients of \(k, k^2 \ldots, k^{n-1}\) in \(P_G(k)\) are all non-zero.

We now consider the case of disconnected graphs.

If \(G=G_1\oplus G_2\oplus \cdots \oplus G_r\) and \(G\) has \(n\) vertices then \[ P_G(k) = k^n - a_1 k^{n-1} + a_2 k^{n-2} - \cdots + (-1)^{n-r}a_{n-r} k^r. \] Moreover, \(a_j \gt 0\) for all \(j=1,\ldots, n-r\).

By Proposition 3.3.4 we have \[ P_G(k) = P_{G_1}(k) P_{G_2}(k) \cdots P_{G_r}(k) \] Since each \(P_{G_i}(k)\) has no constant term, the smallest possible non-zero term in \(P_G(k)\) is \(k^r\). By Theorem 3.3.8, the coefficient of \(k\) in each of \(P_{G_i}(k)\) is non-zero. The coefficient of \(k^r\) in \(P_G(k)\) is the product of the coefficients of \(k\) in \(P_{G_i}(k)\) for \(i=1,2,\ldots,r\). Hence, the coefficient of \(k^r\) in \(P_G(k)\) is non-zero. We now prove that each \(a_j \gt 0\) for \(j=1,2,\ldots, n-r\). The proof is by induction on the number of vertices. The case \(n=1\) is trivial. Assume that the claim holds for all graphs with at most \(n\geq 1\) vertices and let \(G\) be a graph with \(n+1\) vertices and \(r\) components \(G_1,G_2,\ldots, G_r\). Then \(G/e\) is a graph with \(n\) vertices and \(r\) components and \(G-e\) is a graph with \(n+1\) vertices and at least \(r\) components. We may therefore write that \(P_{G-e}(k) = k^{n+1} +\sum_{j=1}^{n+1-r} (-1)^ja_j k^{n+1-j}\) where \(a_j \geq 0\) and by induction \(P_{G/e}(k) = k^n + \sum_{j=1}^{n-r} (-1)^j b_j k^{n-j}\) where \(b_j \gt 0\). Therefore, \[ P_G(k) = k^{n+1} - (a_1 + 1)k^{n} + \sum_{j=1}^{n-r} (-1)^j (a_{j+1} + b_j) k^{n-j} \] and since \(a_1+1 \gt 0\) and \(a_{j+1}+b_j \gt 0 \) for \(j=1,\ldots,n-r\) this proves the claim.

We now discuss some of the properties of the roots of a chromatic polynomial. Let \(\chi = \chi(G)\) and suppose that \(k\) is a non-negative inter. If \(0\leq k \lt \chi\) then there are no colorings \(k\)-colorings and therefore \(P_G(k) = 0\). Thus, there exists integers \(m_j \geq 1\), for \(j=0,1,\ldots,\chi -1\), and a polynomial \(f(z)\) not having \(0,1,\ldots,\chi-1\) as roots such that \[ P_G(z) = z^{m_0}(z-1)^{m_1}\cdots (z-(\chi-1))^{m_{\chi-1}} f(z). \] If \(k\geq\chi\) then \(P_G(k) \gt 0\) and therefore \(f(k) \gt 0\). Thus, \(f\) has no non-negative integer roots. Any negative integer roots of \(P_G\) would therefore be supplied entirely by \(f\). However, the following shows that will not happen.

The chromatic polynomial of any graph does not contain any roots in \((-\infty,0)\).

By Proposition 3.3.4, we can sssume that \(G\) is connected. Thus \[ P_G(x) = x^n + \sum_{j=1}^{n-1} (-1)^j a_j x^{n-j} \] where \(a_j \gt 0\) (by Theorem 3.3.8). Suppose that \(-\lambda \in (-\infty, 0)\) and thus \(\lambda \gt 0\). Then \begin{align*} P_G(-\lambda) &= (-1)^n \lambda ^n + \sum_{j=1}^{n-1} (-1)^j a_j (-1)^{n-j} \lambda^{n-j}\\[2ex] &= (-1)^n \left(\lambda^n + \sum_{j=1}^{n-1} a_j \lambda^{n-j}\right). \end{align*} Since \(\lambda \gt 0\) and \(a_j \gt 0 \) for all \(j=1,\ldots, n-1\), it follows that \(P_G(-\lambda) \neq 0\).

Many graphs, however, have chromatic polynomials with complex roots.

The chromatic polynomial of the graph in Figure 3.3 is \(P_G(x) = x(x-1)(x-2)(x^2-4x+5)\) which has complex roots \(2\pm i\).

figures/complex-chromatic-roots.svg — Graph with complex chromatic roots

For any graph \(G\) of order \(n\) and \(m\) edges, the coefficient of \(k^{n-1}\) in \(P_G(k)\) is \(-m\).

The proof is by induction on the number of edges. If \(G\) has \(m=1\) edges and \(n\) vertices then \(G\) is the union of \(P_2\) and \(E_{n-2}\). Therefore, \[ P_G(k) = P_{P_2}(k) P_{E_{n-2}}(k) = k (k-1) k^{n-2} = k^{n-1}(k-1) = k^n - k^{n-1} \] and the claim follows. Assume that the claim holds for all graphs with at most \(m\geq 1\) edges and suppose that \(G\) has \((m+1)\) edges and \(n\) vertices. By the proof of Lemma 3.3.6, we have \[ P_{G}(k) = k^n - (a_1 + 1)k^{n-1} + \sum_{j=2}^{n-1}(-1)^j k^{n-j}. \] where \(P_{G-e}(k) = k^n - a_1 k^{n-1} + \cdots + (-1)^{n-1}a_{n-1}k\). By induction \(a_1 = m\) and the claim holds.

A graph \(G\) with \(n\) vertices is a tree if and only if \[ P_G(k) = k(k-1)^{n-1}. \]

We first prove that if \(G\) is a tree on \(n\) vertices then \(P_G(k) = k(k-1)^{n-1}\). The proof is by induction on \(n\geq 2\). If \(G=P_2\) then \(P_G(k) = k(k-1)\) and the claim follows. Assume by induction that the claim holds for all trees with at most \(n\geq 2\) vertices and let \(G\) be a tree with \(n+1\) vertices. Since \(G\) is a tree, it has a leaf \(u\) whose neighbor is say \(v\). Let \(e = \{u,v\}\). By the chromatic reduction theorem, \(P_G(k) = P_{G-e}(k) - P_{G/e}(k)\). The graph \(G/e\) is a tree with \(n\) vertices and thus \(P_{G/e}(k) = k(k-1)^{n-1}\). On the other hand, \(G-e\) is the union of a tree on \(n\) vertices and \(K_1\). Thus, by induction we have \(P_{G-e} = k(k-1)^{n-1} k = k^2 (k-1)^{n-1}\). Therefore, \[ P_{G}(k) = k^2 (k-1)^{n-1} - k(k-1)^{n-1} = k(k-1)^{n-1}(k-1) = k(k-1)^n \] and the claim follows. Now suppose that \(G\) has \(n\) vertices and \(P_G(k) = k(k-1)^{n-1}\). Expanding we obtain \[ P_G(k) = k (k^{n-1} - (n-1)k^{n-2} + \cdots + (-1)^{n-1}) = k^n - (n-1)k^{n-1} + \cdots + (-1)^{n-1}k \] and thus by Propositon 3.3.11 we have \(|E(G)| = n-1\). Since the coefficient of \(k\) in \(P_G(k)\) is non-zero, by Theorem 3.3.9 it follows that \(G\) is connected. Hence, \(G\) is a tree.

Use the chromatic reduction theorem to prove that the chromatic polynomial of a cycle \(G=C_n\) is \[ P_G(k) = (k-1)^n + (-1)^n (k-1) \] Solution: For \(n=3\) we have \begin{align*} P_G(k) &= k(k-1)(k-2)\\ & = (k-1+1)(k-1)(k-1-1)\\ &= (k-1+1)(k-1)^2 - (k-1+1)(k-1)\\ & = (k-1)^3 + (k-1)^2 - (k-1)^2 - (k-1) \end{align*} and thus \(P_G(k) = (k-1)^3 + (-1)^3 (k-1)\) as claimed. Assume that the claim holds for \(n\) and consider \(G=C_{n+1}\). For any \(e\in E(C_{n+1})\) we have that \(C_{n+1} - e\) is \(P_{n+1}\) and \(C_{n+1}/e\) is \(C_{n}\). Using the chromatic reduction theorem, the induction hypothesis, and the fact that \(P_{n+1}\) is a tree we obtain \begin{align*} P_G(k) &= k(k-1)^n - \left[ (k-1)^n + (-1)^n (k-1) \right]\\ &= k(k-1)^n - (k-1)^n + (-1)^{n+1}(k-1)\\ &= (k-1)^{n+1} + (-1)^{n+1}(k-1) \end{align*} and this completes the proof.

Show that \(P_{G\vee K_1}(k) = k P_{G}(k-1)\). Use this to find the chromatic polynomial of the wheel graph \(W_n = C_n \vee K_1\).

Exercises

In this question you are going to prove that the chromatic polynomial is an isomorphism invariant.

Suppose that \(G_1\) and \(G_2\) are isomorphic and \(\sigma:V(G_1)\rightarrow V(G_2)\) is an isomorphism. Suppose that \(f:V(G_1)\rightarrow \{1,\ldots,k\}\) is a coloring of \(G_1\). Define the function \(f_{\sigma}:V(G_2)\rightarrow\{1,\ldots,k\}\) by \(f_\sigma(u) = f(\sigma^{-1}(u))\). Prove that \(f_\sigma\) is a coloring of \(G_2\).
Deduce from part (a) that \(P_{G_1}(k) \leq P_{G_2}(k)\).
Now explain why \(P_{G_2}(k)\leq P_{G_1}(k)\).
Conclude.

Let \(C_1, C_2, \ldots, C_k\) be the color classes of a coloring of \(G\). We will say that \(C_i\) is adjacent to \(C_j\) if there exists \(v_i \in C_i\) and \(v_j \in C_j\) such that \(v_i \sim v_j\).

Give an example of a connected graph and a coloring of that graph that produces color classes \(C_1, C_2, \ldots, C_k\) for which there exists some \(C_i\) and \(C_j\) (distinct) that are not adjacent.
Prove that if \(C_1, C_2, \ldots, C_k\) are the color classes of a chromatic coloring of a graph \(G\) (that is, \(k=\chi(G)\)) then \(C_i\) is adjacent \(C_j\) for every distinct color classes \(C_i\) and \(C_j\).
Deduce from part (b) that the number of edges in a graph \(G\) is at least \(\binom{\chi(G)}{2}\).

Provide a proof of Lemma 3.3.7, that is, prove that if \(G\) is connected then \(G/e\) is connected for any \(e\in E(G)\).

Find \(P_G(x)\) if \(G = P_2 \vee E_3\). (Hint: \(G\) is planar so draw it that way.)

Explain why \(P(x) = x^6-12x^5+53x^4-106x^3+96x^2-32x\) is not the chromatic polynomial of any graph \(G\). (Hint: \href{https://www.wolframalpha.com/}{WolframAlpha})

For any graph \(G\), let \(t(G)\) be the number of triangles in \(G\). If \(P_G(k) = k^n + \sum_{j=1}^{n-1} (-1)^j a_j k^{n-j}\) prove that \[ a_2 = \binom{m}{2} - t(G) \] where \(m = |E(G)|\). (Hint: Induct over the number of edges \(m\geq 2\) and use the Chromatic Reduction theorem. You will also need Proposition 3.3.11.)