Skip to main content

Section 4.1 Coloring Vertices

As we have explored in previous sections, graphs are a way to visualize relationships between things. In this section we will explore a way to visualize placing these elements in groups based on their relationships by coloring vertices. You probably have already used coloring vertices to understand problems we have discussed (such as Theorem 2.0.12) by natural inclination. Whenever we want to place our objects into disjoint groups, instead of using group names we can use colors. Let us explore how to color a graph in general.

We will need some definitions:

Definition 4.1.1.

A coloring of a graph is where all vertices are given a color and all adjacent vertices are colored differently.

The chromatic number of a graph written as \(\chi(G)\) is the minimum number of colors that allow you to give a coloring of the vertices.

Example 4.1.2.

Here are two colorings of the same graph.

Note that the chromatic number of the graph is 2, because that is the smallest number of colors that must be used to have a valid coloring.

Activity 16.

Find the chromatic number of the following graphs:

Subsection 4.1.1 Bounds on the Chromatic Number

[Need discussion of the lower bounds, and their limitations (necessary conditions are not sufficient in this case)]

Now let us turn to the question of finding upper bounds for the chromatic number. Certainly, such an upper bound exists, since you will never need more colors than there are vertices in the graph. For the complete graphs, this is the best bound possible. For graphs in general, we can consider the maximum degree in the graph, \(\Delta(G)\text{.}\)

Let \(G\) be any graph with \(n\) vertices. To prove the result, we will induct on \(n\text{.}\)

Base Case: Let \(n=1\text{.}\) Then \(\chi(G)=1\) and \(\Delta(G)=0\) so the inequality holds.

Induction Assumption: Assume that the result holds for all graphs with \(n-1\) vertices and therefore the induction assumption is that \(\chi(G) \le \Delta(G-v)+1\) for some vertex \(v\) in \(G\text{.}\) Meaning that \(G-v\) can be colored by using \(\Delta(G-v)+1\) colors.

Induction Step: Since \(\Delta(G)\) is the maximum degree of a vertex in \(G\text{,}\) vertex \(v\) has at most \(\Delta(G)\) adjacent vertices in \(G\text{.}\) These adjacent vertices can use at most \(\Delta(G)\) colors in the coloring of \(G-v\text{.}\) If \(\Delta(G)=\Delta(G-v)\text{,}\) then there is at least one color not used by \(v\)’s adjacent vertices and that can be used to color \(v\) giving a \(\Delta(G)+1\) coloring. So, in this case, the induction hypothesis, \(\chi(G) \le \Delta(G-v)+1\) becomes, \(\chi(G) \le \Delta(G)+1\text{.}\) In the case \(\Delta(G) \neq \Delta(G-v)\text{,}\) then \(\Delta(G-v) \lt \Delta(G)\text{.}\) Therefore, using a new color for \(v\) we have that \(\Delta(G-v)+1+1=\Delta(G-v)+2\) coloring of \(G\text{.}\) Then \(\Delta(G-v)+2 \le \Delta(G)+1\text{.}\) Lastly, the induction hypothesis says that \(\chi(G) \le \Delta(G-V)+1\) and certainly \(\Delta(G-v) \le \Delta(G-v)+2\text{.}\) Hence \(\chi(G) \le \Delta(G)+1\text{.}\)

If a graph is complete, then \(\chi(G) = \Delta(G) + 1\text{.}\) Similarly, if \(G\) is an odd cycle, then \(\chi(G) = 3\) and \(\Delta(G) = 2\text{.}\) So it seems like we cannot improve the bound above. However, it turns out that it is only these two cases that give us equality in the bound.

This proof is based on the proof in Diestel's Graph Theory.

Suppose the theorem is not true, and let \(G\) be a minimal counterexample. That is, assume \(G\) is not complete or an odd cycle, but that \(\chi(G) \gt \Delta(G)\text{,}\) while for all graphs with fewer vertices, the theorem does hold.

Consider any vertex \(v \in G\) and consider the graph \(G' = G - v\text{.}\) The theorem holds for each connected component of \(G'\text{,}\) so \(\chi(G') \le \Delta(G)\text{,}\) since \(\chi(G') \le \Delta(G') \le \Delta(G)\)

Since \(\chi(G') \le \Delta(G)\) but \(\chi(G) \gt \Delta(G)\text{,}\) we must have the following;

  1. In fact, \(\chi(G') = \Delta(G)\) and \(d(v) = \Delta(G)\text{,}\) since removing \(v\) can only reduce \(\chi(G)\) by at most one. Further, every \(\Delta(G)\)-coloring of \(G'\) must use all \(\Delta(G)\) colors on the neighbors of \(v\text{,}\) otherwise we would have colored \(v\) with one of our \(\Delta(G)\) colors from the start and a \(\Delta(G)\) coloring of \(G\) would have existed.

  2. For any particular \(\Delta(G)\)-coloring of \(G'\text{,}\) let \(v_i\) be the neighbor of \(v\) colored \(i\) and let \(H_{i,j}\) (for \(i\ne j\)) be the subgraph of \(G\) spanned by the vertices colored \(i\) and \(j\text{.}\)

    For each \(i \ne j\text{,}\) we have that \(v_i\) and \(v_j\) belong to the same connected component \(C_{i,j}\) of \(H_{i,j}\text{.}\) This is because if \(v_i\) and \(v_j\) did not belong to the same connected component \(C_{i,j}\) of \(H_{i,j}\text{,}\) we would be able to swap colors and free up a color for \(v\) by changing the vertex colored \(j\) to \(i\text{.}\)

  3. For each \(i\ne j\text{,}\) we have that \(C_{i,j}\) is a path from \(v_i\) to \(v_j\text{,}\) otherwise \(C_{i,j}\) would not be connected. This would again lead to either color \(i\) or \(j\) being freed up by a swap.

  4. For distinct \(i,j,k\text{,}\) the components \(C_{i,j}\) and \(C_{i,k}\) intersect only in \(v_i\text{,}\) otherwise an alternating path within a component can be swapped to free up a color for \(v\text{.}\)

  5. For some \(i \ne j\text{,}\) the vertices \(v_i\) and \(v_j\) are not adjacent. This is because if all \(v_i\) and \(v_j\) are adjacent, then \(v\) would not have been of max degree.

Fix a \(\Delta(G)\)-coloring \(c\) of \(G'\text{.}\) Without loss of generality, assume \(v_1\) is not adjacent to \(v_2\text{.}\) Define a new coloring \(c'\) of \(G'\) that simply swaps the colors \(1\) and \(3\) along \(C_{1,3}\text{,}\) and define \(v_i'\text{,}\) \(H_{i,j}'\text{,}\) and \(C_{i,j}'\) in the obvious way.

Let \(u\) be the neighbor of \(v_1 = v_3'\) in \(C_{1,2}\text{.}\) Then \(u \in C_{1,2}' \cap C_{2,3}'\) by the fourth condition above, yielding a contradiction. Therefore there exists an alternating path whose colors can be swapped until that intersection, thus freeing up a color for \(v\) and allowing \(G\) to be be colored such that \(\chi(G) \le \Delta(G)\text{.}\)