JaewookFor a graph \(G\), let us write \(\chi (G)\) for the minimum number of colors we need to color the vertices of graphs without adjacent vertices having the same color, and \(\chi’ (G)\) for the minimum number of colors we need to color the edges of graphs without edges sharing a vertex having the same color (both of which we will formally define later).
Both of these quantities are closely related to the maximum vertex degree of the graph \(G\), which we denote by \(\Delta(G)\), as surprisingly concisely demonstrated in the following theorems by Brooks (1941) and Vizing (1965).
Theorem 1. (Brooks, 1941) For almost all simple (connected) graphs \(G\), we have $$\chi (G) \le \Delta(G),$$ only except odd cycles and complete graphs where $$\chi (G) = \Delta(G) + 1.$$
Theorem 2. (Vizing, 1965) For all simple graphs \(G\), we have $$\Delta (G) \le \chi’ (G) \le \Delta(G) + 1.$$
Note. I am not an expert in discrete math and graph theory at all, but I decided to write this post as I had lots of fun taking graph theory classes when I was an undergrad. Please tell me if something is wrong, or there is anything else anyone would like to add!
Basic Notations & Definitions
These are some basic notations we will use throughout the article.
- We denote the vertices and edges of \(G\) by \(V(G)\) and \(E(G)\), respectively.
- We write \(G \backslash e\) with \(e \in E(G)\) for the graph with the edge \(e\) removed from \(G\).
- We write \(G \backslash v\) with \(v \in V(G)\) for the graph with the vertex \(v\) and all edges connected to \(v\) from \(G\).
- We denote the neighborhood of \(v \in V(G)\) by $$N_G (v) = \{w \in V(G): vw \in E(G) \}.$$
- We denote the maximum degree of the vertices in \(G\) by $$\Delta(G) := \max_{v \in V(G)} \deg_{G} v.$$
We will assume in most cases that the graph \(G\) of our interest is simple and connected, which is defined as below.
- A graph \(G\) is simple if it has no loops or parallel edges.
- A graph \(G\) is connected if there does not exist a nonempty partition \(A, B\) of \(V(G)\) such that \(G\) has no edges joining \(A\) and \(B\).
There are also some special types of graphs we will mention throughout the article.
- A cycle is a connected graph with all vertices having degree \(2\). (Some might prefer a more formal definition, but let’s keep it simple here.)
- A path is a connected graph with all vertices having degree \(2\) except for the two endpoints with degree \(1\). (Same here as well)
- A complete graph has all possible edges between any two vertices. We denote complete graphs with \(n\) vertices by \(K_{n}\).
- A bipartite graph has a nonempty partition \(A, B\) of \(V(G)\) such that \(G\) has no edges joining two vertices in \(A\) or two vertices in \(B\).
Vertex Colorings
We first define some concepts related to vertex colorings of a graph.
- Let \(S\) be a set of colors. A vertex coloring of a graph \(G\) is a function \(c: V(G) \rightarrow S\) such that \(c(v) \ne c(w)\) if the vertices \(v, w\) are adjacent.
- If \(S = \{1, \dots, k\}\), we say that \(c\) is a \(k\)-coloring.
- We say that a graph \(G\) is \(k\)-colorable if it admits a \(k\)-coloring.
- The chromatic number of a graph is defined as $$\chi(G) = \min k \ \ \text{s.t.} \ G \text{ is } k \text{-colorable.}$$
Thus, \(\chi(G)\) tells us that a graph \(G\) admits a \(\chi(G)\)-coloring but does not have a \(\chi(G)-1\)-coloring of any kind. The famous four color theorem, for example, states that \(\chi(G) \le 4\) whenever \(G\) is a planar graph, which is also a very interesting topic but sadly will not be covered in this post.
It is easy to show an upper bound \(\chi(G) \le \Delta(G) + 1\) for all simple graphs \(G\) by a simple proof using induction on \(|V(G)|\), the number of vertices of \(G\).
Fact. Every simple graph \(G\) has \(\chi(G) \le \Delta(G) + 1\).
Proof. We use induction on \(|V(G)|\). The theorem is trivial for the base cases \(|V(G)| \le 1\), so we may assume that \(|V(G)| \ge 2\) and the induction hypothesis holds for graphs with a lesser number of vertices.
Let \(v \in V(G)\) be any vertex. By the induction hypothesis, \(G \backslash v\) has a \(\Delta(G) + 1\)-coloring. Since \(\deg_{G} v \le \Delta(G)\), there exists an unused color among neighbors of \(v\) with which we can color \(v\) to obtain a \(\Delta(G) + 1\)-coloring. \(\square\)
The basic idea is that \(\Delta(G) + 1\) colors are enough to freely color any vertex and its neighbors with different colors. What’s more interesting is that we can obtain a stronger upper bound of \(\chi(G) \le \Delta(G)\) for almost all graphs, only excluding odd cycles and complete graphs where it is obvious that \(\chi(G) = \Delta(G) + 1\). This is known as Brooks’ theorem, and we can prove this via a more careful induction argument on \(|V(G)|\).
Theorem 1. (Brooks, 1941) A simple connected graph has \(\chi(G) \le \Delta(G)\) unless it is a complete graph or a cycle of odd length.
Proof. First, if \(\Delta(G) \le 2\), then the statement is trivial because odd cycles cannot be \(2\)-colored (whereas even cycles can). Therefore we may assume that \(\Delta(G) \ge 3\) and we are left to show the following claim for each fixed \(\Delta \ge 3\).
Claim. If \(G\) is connected, \(\Delta(G) = \Delta \ge 3\), and \(\deg_{G} v \le \Delta\) for all \(v \in V(G)\), then \(\chi(G) \le \Delta\) unless \(G = K_{\Delta + 1}\).
We prove this claim by induction on \(|V(G)|\).
If \(|V(G)| = \Delta + 1\), we have either \(G = K_{\Delta + 1}\) or there exists two vertices \(v_{i}, v_{j}\) of \(v\) that are not adjacent to each other. For the latter case, we can color \(v_{i}, v_{j}\) with a certain color and use the rest of the \(\Delta {}-{} 1\) colors exactly once for each of the remaining vertices to obtain a \(\Delta\)-coloring of \(G\), which covers the base case.
Suppose that there exists \(v \in V(G)\) such that \(\deg_{G} v \le \Delta {}-{} 1\). Then by the induction hypothesis we have a \(\Delta\)-coloring of \(G \backslash v\), and we can use an unused color among the neighbors of \(v\) to obtain a \(\Delta\)-coloring of \(G\).
Therefore we may assume that \(\deg_{G} v = \Delta\) for all \(v \in V(G)\), i.e., \(G\) is \(\Delta\)-regular.
Suppose that, for any vertex \(v \in V(G)\), there exists a \(\Delta\)-coloring of \(G \backslash v\) such that the neighbors \(N_{G} (v)\) use \(\Delta {}-{} 1\) or less colors, i.e., there exists an unused color. Note that \(|N_{G} (v)| = \Delta\) as we assume that \(G\) is \(\Delta\)-regular. Then we can color \(v\) with that unused color to obtain a \(\Delta\)-coloring of \(G\).
Therefore we may assume that for any fixed \(v \in V(G)\) and any \(\Delta\)-coloring of \(G \backslash v\), all \(\Delta\) colors appear in the neighbors \(N_{G} (v)\) exactly once.
Let us choose any vertex \(v \in V(G)\). By the above assumption, we may denote by \(v_{i}\) the neighbor of \(v\) with color \(i\) for each \(i \in S = \{1, \dots, \Delta\}\). Define \(H_{ij}\) as the subgraph of \(G\) induced by vertices of color \(i\) or \(j\) and \(C_{ij}\) as the connected component of \(H_{ij}\) which contains \(v_{i}\).
Suppose that \(v_{j} \notin C_{ij}\). Then we can swap the colors \(i\) and \(j\) only inside \(C_{ij}\), which changes the color of \(v_{i}\) to \(j\) while maintaining a valid \(\Delta\)-coloring. After this, we can color \(v\) with \(i\) to obtain a \(\Delta\)-coloring of \(G\).
Therefore we may assume that \(v_{j} \in C_{ij}\), i.e., \(C_{ij} = C_{ji}\) for all colors \(i \ne j\) of any \(\Delta\)-coloring of \(G \backslash v\).
Suppose that there exists \(i \ne j\) such that \(v_{i}\) has two or more neighbors in \(C_{ij}\) (of color \(j\), by definition). This means that \(N_{G} (v_i)\) uses at most \(\Delta {}-{} 1\) colors, and therefore we may recolor \(v_{i}\) with the unused color. After this, we can color \(v\) with \(i\) to obtain a \(\Delta\)-coloring of \(G\).
Therefore we may assume that \(\deg_{C_{ij}} v_{i} = 1\) for all colors \(i \ne j\). Note that this also implies \(\deg_{C_{ij}} v_{j} = 1\) by symmetry, i.e., \(C_{ij} = C_{ji}\) for any \(\Delta\)-coloring of \(G \backslash v\).
Suppose that \(C_{ij}\) contains a vertex with degree \(\ge 3\). Among such vertices, choose the one \(w\) with the minimum edge distance to \(v_{i}\). Since \(w \in C_{ij}\), we have that either \(w\) is colored with \(i\) and at least \(3\) neighbors in \(N_{G} (w)\) are colored with \(j\), or vice versa. Then we have \(\Delta {}-{} 3\) remaining neighbors and \(\Delta {}-{} 2\) remaining colors excluding \(i, j\), which means that there exists at least one unused color in \(N_{G} (w)\).
We can recolor \(w\) with this unused color (which is different from \(i, j\)) and redefine the components \(C_{ij}’\) for the new coloring. Note that by the minimality of the distance of \(w\) to \(v_{i}\), all vertices between \(v_i\) and \(w\) must have degree \(2\), and \(v_{j}\) is never included in the path (as \(\deg_{C_{ij}} v_{j} = 1\)). Hence removing \(w\) from \(C_{ij}\) leads to \(C_{ij}’ \ne C_{ji}’\), which then yields a \(\Delta\)-coloring of \(G\) by swapping colors in \(C_{ij}’\) as we did above.
Therefore we may assume that \(C_{ij}\) is a path between \(v_{i}\) and \(v_{j}\) for all colors \(i \ne j\) of any \(\Delta\)-coloring of \(G \backslash v\). Note that since the endpoints are of different colors, these paths must always have an odd length, alternating between vertices colored with \(i\) and \(j\).
Suppose that there exists \(w \ne v_{i}\) with \(w \in V(C_{ij}) \cap V(C_{ik})\) for distinct colors \(i, j, k\). By definition \(w\) must have color \(i\) (in order to be contained in both \(C_{ij}\) and \(C_{ik}\)), and it has \(2\) neighbors in \(N_{G} (w)\) with color \(j\) and \(2\) of those with color \(k\). Then we have \(\Delta {}-{} 4\) remaining neighbors and \(\Delta {}-{} 3\) remaining colors excluding \(i, j, k\), which means that there exists at least one unused color in \(N_{G} (w)\).
Just as we did right above, we can recolor \(w\) with this unused color, redefine the components \(C_{ij}’\), observe that \(C_{ij}’ \ne C_{ji}’\) (and \(C_{ik}’ \ne C_{ki}’\) as well), and obtain a \(\Delta\)-coloring of \(G\) by swapping colors in \(C_{ij}’\).
Therefore we may assume that \(V(C_{ij}) \cap V(C_{ik}) = \{ v_{i} \}\) for all distinct colors \(i, j, k\) of any \(\Delta\)-coloring of \(G \backslash v\).
Now this is precisely where we have to exclude the case \(G = K_{\Delta + 1}\) to proceed; if \(G\) is a \(\Delta\)-regular graph and all neighbors \(v_{i}\) of \(v\) are adjacent, then \(G\) simply becomes a \(K_{\Delta + 1}\) with vertices \(V(G) = \{ v, v_{1}, \dots, v_{\Delta} \}\). Therefore, if \(G\) is a \(\Delta\)-regular graph with \(G \ne K_{\Delta + 1}\), we can always find two neighbors \(v_{i}, v_{j}\) of \(v\) that are not adjacent to each other. From now we denote those two specific vertices by \(v_{i}, v_{j}\).
Given any \(\Delta\)-coloring of \(G \backslash v\), suppose that \(G’\) is a graph with a new coloring, where colors \(i\) and \(k\) are swapped only in \(C_{ik}\) for some \(k \notin \{i, j\}\).
Let \(u\) be the neighbor of \(v_{i}\) in \(C_{ij}\). Note that \(u \ne v_{j}\) as \(v_{i}, v_{j}\) are not adjacent.
- As the \(v_{j}\) side of \(C_{ij}\) remains in the new coloring, we have \(u \in V(C_{ij}’)\).
- As \(u\) is connected (by adjacency) to \(v_{k}’ = v_{i}\), we have \(u \in V(C_{jk}’)\).
This implies that \(u \in V(C_{ij}’) \cap V(C_{jk}’)\) and thus \(u = v_{j}\), which is a contradiction with \(u \ne v_{j}\).
Therefore we have shown that we can always obtain a \(\Delta\)-coloring of \(G\), which proves the given statement by induction. \(\square\)
One may wonder if there could be a lower bound of \(\chi(G)\) that depends on \(\Delta(G)\). The answer is simple; for the case of vertex colorings, it is easy to see that bipartite graphs always satisfy \(\chi(G) \le 2\), regardless of how large \(\Delta(G)\) may get. (In fact, a graph is bipartite if and only if \(\chi(G) \le 2\).)
Edge Colorings
Similarly as in the vertex coloring part, we define some concepts related to edge colorings of a graph.
- Let \(S\) be a set of colors. An edge coloring of a graph \(G\) is a function \(c: E(G) \rightarrow S\) such that \(c(e) \ne c(e’)\) if the edges \(e, e’\) share a vertex.
- If \(S = \{1, \dots, k\}\), we say that \(c\) is a \(k\)-edge-coloring.
- We say that a graph \(G\) is \(k\)-edge-colorable if it admits a \(k\)-edge-coloring.
- The edge chromatic number of a graph is defined as $$\chi’ (G) = \min k \ \ \text{s.t.} \ G \text{ is } k \text{-edge-colorable.}$$
Now let us prove Vizing’s theorem on graph edge colorings.
Theorem 2. (Vizing, 1965) A simple graph has \(\Delta(G) \le \chi’ (G) \le \Delta(G) + 1\).
Proof. It is trivial that \(\Delta(G) \le \chi’ (G)\) because the vertex attaining the maximum degree must be connected to exactly \(\Delta (G)\) edges which must all have different colors. Thus we are left to show the upper bound of \(\chi’ (G) \le \Delta(G) + 1\).
For simplicity, we will say that a color \(c\) is absent at a vertex \(v\) if, given an edge coloring of \(G\), no edge connected to \(v\) has the color \(c\). The key idea of the proof is that, if we are given \(\Delta (G) + 1\) (or more) colors, every vertex must always have at least one absent color. This allows us to use induction to find a nice sequence of edges so that, from an edge coloring of \(G \backslash e\) for some edge \(e\), we can smartly rearrange the colors to obtain an edge coloring of \(G\).
Now we will first show the following statement, which is a bit stronger than and naturally leads to Vizing’s theorem.
Claim. If \(G \backslash e\) is \(K\)-edge-colorable for \(K \ge \Delta(G) + 1\) and some edge \(e \in E(G)\), then \(G\) is \(K\)-edge-colorable.
Suppose that we are given a \(K\)-edge-coloring of \(G \backslash e\), where \(K \ge \Delta(G) + 1\) and \(e = vw_0\) is an edge of \(G\). Note that since \(K \ge \Delta(G) + 1\), it remains that every vertex must always have at least one absent color. From this coloring of \(G \backslash e\) where \(e = vw_0\) is not colored yet, our goal is to construct a \(K\)-edge-coloring of \(G\) using a nice technique often referred to as Kempe chains.
Let us write \(e_0 = vw_0\) instead of \(e\) from now on. Denote the absent color in the vertex \(w_0\) by \(c_0\) and \(v\) by \(c_v\). Then, we construct a chain of edges \(e_i = vw_i\) as follows.
- Choose \(e_{i+1} = vw_{i+1}\) as the edge with color \(c_i\) that is absent in \(w_i\).
- Stop if either (i) \(c_{k}\) is absent in \(v\), or (ii) \(c_{k} = c_{j-1}\) for some \(j < k\).
If the chain stops and \(c_{k}\) is absent in \(v\), we are done since we can shift the colors in the chain by recoloring \(e_i\) with \(c_i\) for all \(i = 0, \dots, k\) to obtain a \(K\)-edge-coloring of \(G\).
While this is an easy step, it would be helpful to remember this shape as we will use a similar recoloring scheme to complete the proof for the other cases.
Therefore we may assume that the chain stops for some \(j < k\) such that \(c_{k} = c_{j-1}\), i.e., \(c_{k}\) is already used in an edge \(e_j = vw_j\). This color is automatically different from \(c_{v}\), and is absent in both \(w_{j-1}\) and \(w_k\).
Define \(H\) as the subgraph of \(G\) induced by edges of color \(c_{k}\) and \(c_{v}\). Since this subgraph is from an edge coloring, the maximum degree of vertices in \(H\) is at most \(2\), and thus the components of \(H\) must either be a cycle or a path. (These types of subgraphs with \(2\)-edge-colorings are often called Kempe chains.)
Let \(C\) be the component of \(H\) that contains \(e_j\). Then \(C\) cannot be a cycle, as the color \(c_v\) is absent in endpoint \(v\). Therefore \(C\) is a path that ends in some vertex \(u\) in \(G\). Now let us think of a new coloring, where we swap the colors \(c_{k}\) and \(c_{v}\) in the path \(C\). (These kinds of swaps are sometimes called Kempe changes.) This is still a valid coloring because the endpoint \(u\) must have all edges outside \(C\) with colors that are neither \(c_{k}\) nor \(c_{v}\); if not, it cannot be the endpoint of the path \(C\). Observe that for the new coloring, \(c_{k}\) is absent in \(v\) (instead of \(c_{v}\)).
Suppose that \(u \ne v_{j-1}\). Then we have the following facts for the new coloring.
- \(c_{k}\) is absent in both \(v\) and \(w_{j-1}\)
- \(c_{i}\) is absent in \(w_{i}\) for \(i = 0, \dots, j-2\) (unchanged)
Therefore we can shift the colors in the chain by recoloring \(e_{j-1}\) with \(c_k\), and then \(e_i\) with \(c_i\) for all \(i = 0, \dots, j-2\).
Therefore we may assume that \(u = v_{j-1}\). Then for the new coloring, while \(c_{k}\) is absent in \(v\) as in the previous case, the key difference is that the color absent in \(v_{j-1}\) also changes to \(c_{v}\) by the color swap. This time, we have the following facts for the new coloring.
- \(c_k\) is absent in both \(v\) and \(w_{k}\)
- \(c_{i}\) is absent in \(w_{i}\) for \(i = j, \dots, k-1\) (unchanged)
- \(c_{v}\) is absent in \(w_{j-1}\), and \(e_{j} = vw_{j}\) is colored with \(c_{v}\)
- \(c_{i}\) is absent in \(w_{i}\) for \(i = 0, \dots, j-2\) (unchanged)
Therefore we can shift the colors in the chain by recoloring \(e_{j-1}\) with \(c_v\), and \(e_i\) with \(c_i\) for all \(i \ne j-1\).
Hence we have shown that there always exists a \(K\)-coloring of \(G\), which proves our Claim.
Finally, to prove the original statement in Vizing’s theorem, we use induction on \(|E(G)|\). When \(E(G) = 0\), the theorem statement is trivial. When we have a \(\Delta(G \backslash e) + 1\)-edge-coloring of \(G \backslash e\) (which is also a \(\Delta(G) + 1\)-edge coloring because \(\Delta(G \backslash e) + 1 \le \Delta(G) + 1\)) by the induction hypothesis, by Claim we can obtain a \(\Delta(G) + 1\)-edge coloring of \(G\), which completes the proof. \(\square\)
Unlike the case of vertex colorings, here we only have two possible choices; we must either have \(\chi'(G) = \Delta(G)\) or \(\chi'(G) = \Delta(G) + 1\). This allows us to classify the family of simple graphs largely into two classes.
Definition. Graphs that can be colored with \(\Delta(G)\) colors are called class one graphs. Graphs that require \(\Delta(G) + 1\) colors are called class two graphs.
Whlie it is known that almost all graphs are of class one in terms of random graph theory, we can sometimes provably classify some special types of graphs into one of these two classes. There is much more that could be said about more classical results and some recent progress on graph colorings, but today I would like to end this article with two simple theorems that each show how and why certain graphs must be in either class one or two, respectively. Enjoy!
Theorem 3. (Kőnig, 1916) A bipartite graph \(G\) is in class one.
Proof. Suppose by contradiction that there exists a counterexample. Let \(G\) be a bipartite graph in class two of minimal size with \(\Delta(G) = \Delta\), and \(e = vw\) be an edge so that \(G \backslash e\) is in class one (by the minimality of \(G\)), i.e., \(\chi’ (G \backslash e) = \Delta (G \backslash e)\).
Among a set of \(\Delta\) colors, if there is an unused color in the collection of edges connected to either \(v\) or \(w\), we can use this color in \(vw\) to obtain a \(\Delta\)-edge-coloring of \(G\) and thus \(G\) must be in class one.
Therefore we may assume that \(\Delta\) colors appear in the collection of edges connected to either \(v\) or \(w\).
Since we have removed the edge \(e = vw\) from a graph \(G\) with maximal degree \(\Delta\), we have \(\deg_{G \backslash e} v \le \Delta {}-{} 1\) and \(\deg_{G \backslash e} w \le \Delta {}-{} 1\). Thus there each exists a color \(c_v\) absent in \(v\) and a color \(c_w\) absent in \(w\), where \(c_v\) is present (not absent) at \(w\) and vice versa.
Define \(H\) as the subgraph of \(G\) induced by edges of color \(c_{v}\) and \(c_{w}\), and \(C\) as the component of \(H\) containing \(w\). As stated in Vizing’s theorem, \(C\) has maximum degree \(\le 2\) and thus \(C\) must either be a cycle or a path. Because \(c_w\) is absent in \(w\), we have that \(C\) is a path (as it cannot be a cycle) and \(w\) must be an endpoint.
Suppose that \(v \in C\). Then \(v\) must also be an endpoint because \(c_v\) is absent at \(v\). Because \(G\) is a bipartite graph and \(vw \in E(G)\), the path must be of odd length. (A path must alternate between two disjoint sets of vertices in bipartite graphs, and \(vw\) is an edge of \(G\) which means that \(v\) and \(w\) must be in different sets.) This is a contradiction because then the edge connected to \(v\) must also be colored with \(c_v\).
Therefore we may assume that \(v \notin C\).
Now let us swap the colors \(c_{v}\) and \(c_{w}\) in \(C\). Then for the new coloring, we have that \(c_v\) is absent in both \(v\) and \(w\) this time. Therefore we can color \(vw\) with \(c_{v}\) to obtain a \(\Delta\)-edge-coloring of \(G\) and thus \(G\) must be in class one.
Hence we have a contradiction, which completes the proof. \(\square\)
Theorem 4. A regular graph on an odd number of vertices is in class two.
Proof. Suppose that \(G\) is a \(\Delta\)-regular graph with \(n = 2m+1\) vertices for some \(m\). Then \(G\) must have \(\frac{\Delta(2m+1)}{2}\) edges, and thus \(k\) must be even, i.e., \(\Delta = 2 \ell\) for some \(\ell\), and we can write the number of edges as \(\ell (2m+1)\).
Now, suppose by contradiction that we have a \(\Delta\)-edge-coloring of \(G\). As the average number of edges per color is \(\frac{\ell (2m+1)}{k} = m+\frac{1}{2}\), there exists at least one color that appears on \(m+1\) edges. Since \(G\) has \(2m+1\) vertices, one of these edges must share a vertex, which is a contradiction. \(\square\)
References
Brooks, R. L. On colouring the nodes of a network. Proceedings of the Cambridge Philosophical Society (1941), 37 (2): 194–197.
Kőnig, D. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére. Matematikai és Természettudományi Értesítő (1916), 34: 104–119.
Vizing, V. G. Critical Graphs with Given Chromatic Class. Diskret, Analiz 5 (1965), pp. 9–17.
