New Note
It is not particularly difficult to show that the map drawn in Figure 10.3 can be colored with four colors, that is, each region of the map can be assigned one of four given colors such that neighboring regions are colored differently. Indeed, one such coloring is shown in the figure, where r, b, g and y denote red, blue, green and yellow, respectively. What does coloring the regions of a map have to do with graphs? Actually, there is a close connection. With each map, there is associated a graph G, called the dual of the map, whose vertices are the regions of the map and such that two vertices of G are adjacent if the corresponding regions are neighboring regions. The dual of the map in Figure 10.3 is also shown in the figure. Observe that the graph G of Figure 10.3 is a connected planar graph. In fact, the dual of every map is a connected planar graph. Conversely, every connected planar graph is the dual of some map. Indeed, representing the regions of a map and adjacency of regions by a graph actually occurred in the 1879 paper of Kempe. The term “graph” was evidently used for the first time only a year earlier by James Joseph Sylvester.
Figure 10.3: A map and its dual
Coloring the regions of a map suggests coloring the vertices of its dual. Indeed, it suggests coloring the vertices of any graph. By a proper coloring (or, more simply, a coloring) of a graph G, we mean an assignment of colors (elements of some set) to the vertices of G, one color to each vertex, such that adjacent vertices are colored differently. The smallest number of colors in any coloring of a graph G is called the chromatic number of G and is denoted by (G). (The symbol is the Greek letter “chi.”) If it is possible to color (the vertices of) G from a set of k colors, then G is said to be k-colorable. A coloring that uses k colors is called a k-coloring. If (G) = k, then G is said to be k- chromatic and every k-coloring of G is a minimum coloring of G.
Figure 10.3 shows a coloring of a graph G, namely, a coloring of the dual of the map in Figure 10.3. Necessarily then, G is 4-colorable; indeed, G is 4-chromatic. In fact, the coloring of G in Figure 10.3 is suggested by the coloring of the map. Hence the Four Color Theorem gives us the following result, which is then a restatement of this famous theorem.
Theorem 10.1 (The Four Color Theorem) The chromatic number of every planar graph is at most 4.
We have already mentioned that the origin of the Four Color Conjecture goes back to 1852. At one time, however, there were some who believed the origin went back even farther. This is not so, but the confusion may be understandable. In 1840 August Möbius (1790–1868) posed a problem that is sometimes referred to as:
The Problem of the Five Princes
There once was a king who had five sons. In his will he stated that on his death his kingdom should be divided into five regions for his sons in such a way that each region
should have a common boundary with the other four. How can this be done?
If a solution to this problem is not evident, then it might be interesting to look at an extension of this problem that was posed by Heinrich Tietze (1880-1964), a prominent topologist:
The Problem of the Five Palaces
The king additionally required each of his five sons to build a palace in his region and the sons should link each pair of palaces by roads so that no two roads cross. How can this be done?
The Problem of the Five Palaces can be modeled by a graph G whose vertices are the palaces and whose edges are the roads. Then G = K5. A solution to this problem requires G to be planar, which it
is not. The graph G is the dual graph of any solution to the Problem of the Five Princes. This says that neither problem has a solution. To divide the kingdom into five regions in this manner would require five colors to color the regions. However, there is no such configuration of five regions. What this statement says is that no map can contain five regions, every two of which are neighboring. This does not solve the Four Color Problem, however, because what the statement does not say is that there can’t be some other configuration of regions that might require five colors. This is where the difficulty lies.
Let’s make a few observations about coloring graphs and the chromatic numbers of some familiar graphs. First, if a graph G contains even one edge, then at least two colors are required to color G. That is, (G) = 1 if and only if for some positive integer n.
In any coloring of a graph G, no two vertices that are colored the same can be adjacent. Sets of vertices, no two of which are adjacent, are necessarily of interest to us when discussing coloring. Recall that a set S of vertices in a graph G is independent if no two vertices of S are adjacent. Ordinarily, a graph has many independent sets of vertices. Recall also that a maximum independent set is an independent set of maximum cardinality. The number of vertices in a maximum independent set of G is denoted by (G) and is called the vertex independence number (or, more simply, the independence number) of G. For the graph G = C6 of Figure 10.4, S1 = {v1, v4} and S2 = {v2, v4, v6}
are both independent sets. Since no independent set of G contains more than three vertices, (G) = 3. If G is a k-chromatic graph, then it is possible to partition V(G) into k independent sets V1, V2, ...,
Vk, called color classes, but it is not possible to partition V(G) into k − 1 independent sets. Typically, we think of the vertices in the color class Vi (1 ≤ i ≤ k) as being assigned color i. Conversely, if G is a
Figure 10.4: Independent sets
graph whose vertex set can be partitioned into k independent sets, but no fewer, then (G) = k.
Therefore, in order for a graph G to have chromatic number 2, the graph G must be nonempty and it must be possible to partition V(G) into two independent sets V1 and V2. Consequently, every edge of
G must join a vertex of V1 and a vertex of V2. But this means that G is a bipartite graph with partite sets V1 and V2.
Theorem 10.2 A graph G has chromatic number 2 if and only if G is a nonempty bipartite graph.
By Theorem 1.12, a graph G is bipartite if and only if G has no odd cycles. So if a graph G contains an odd cycle, then (G) ≥ 3. Of course, if G = Cn for some even integer n ≥ 4, then (G) = 2.
On the other hand, if n ≥ 3 is an odd integer, then (Cn) = 3. We already know that (Cn) ≥ 3 when n ≥ 3 is an odd integer. To show that (Cn) = 3, we need only show that there exists a 3-coloring of Cn. Actually, we can color some vertex of Cn with the color 3 and alternate the colors 1 and 2 for the remaining vertices (see Figure 10.5).
Figure 10.5: The chromatic numbers of odd cycles
The way we established the chromatic number of Cn for each odd integer n ≥ 3 illustrates how to
establish the chromatic number of any graph. To show that (G) = k for some graph G and some integer k ≥ 3, we must show that
(1) at least k colors are needed to color G (or, equivalently, show that it is impossible to color G with k − 1 colors) and
(2) there is a k-coloring of G.
Example 10.3 The graph G shown in Figure 10.6 is 3-chromatic.
Figure 10.6: A 3-chromatic graph G
Solution. Since G contains a triangle, it follows that (G) ≥ 3. On the other hand, a 3-coloring of G is shown in Figure 10.6, implying that (G) ≤ 3. Therefore, (G) = 3.
Some comments concerning the solution of Example 10.3 may be useful. As we said, G contains a triangle, which implies that (G) ≥ 3. Therefore, to show that (G) = 3, it suffices to present a 3- coloring of G. Of course, a 3-coloring of G is shown in Figure 10.6. However, we didn’t initially know that such a coloring was possible. This graph G also contains a 5-cycle, which requires three colors. Perhaps we thought of 3-coloring this 5-cycle first. There is a number of ways to 3-color this 5-cycle. One of these is shown in Figure 10.7(a). If we now attempt to color the remaining vertices of G so that only three colors are used, then the resulting coloring produces two adjacent vertices that are colored 3 as shown in Figure 10.7(b), which is impossible. This might have led us to conclude (incorrectly) that (G) = 4. This indicates that care must be taken when coloring a graph.
Figure 10.7: Coloring a graph
A useful application of coloring occurs in certain kinds of scheduling problems.
Example 10.4 The mathematics department of a certain college plans to schedule the classes Graph Theory (GT), Statistics (S), Linear Algebra (LA), Advanced Calculus (AC), Geometry (G) and Modern Algebra (MA) this summer. Ten students (see below) have indicated the courses they plan to take. With this information, use graph theory to determine the minimum number of time periods needed to offer these courses so that every two classes having a student in common are taught at different time periods during the day. Of course, two classes having no students in common can be taught during the same period.
Solution. First, we construct a graphH whose vertices are the six subjects. Two vertices (subjects) are joined by an edge if some student is taking both classes (see Figure 10.8). The minimum number of time periods is (H). Since H contains the odd cycle (GT, S, AC, G, MA, GT), it follows that three colors are needed to color the vertices on this cycle. Since LA is adjacent to all vertices of this cycle, a fourth color is needed for LA. Thus (H) ≥ 4. However, there is a 4-coloring of H shown in Figure 10.8 and so (H) = 4. This also tells us one way to schedule these six classes during four time periods, namely, Period 1: Graph Theory, Advanced Calculus; Period 2: Geometry; Period 3: Statistics, Modern Algebra; Period 4: Linear Algebra.
Figure 10.8: The graph of Example 10.4
Certainly, every graph G of order n is n-colorable. If G = Kn, then every two vertices must be
assigned different colors and so (Kn) = n. If G has order n and G ≠ Kn, then G contains two
nonadjacent vertices, say u and v. Assigning u and v the color 1 and the remaining n − 2 vertices the colors2,3,...,n−1producesan(n−1)-coloringofGandso (G)≤n−1.Thatis,agraphGof order n has chromatic number n if and only if G = Kn.
Another observation is useful. If H is a subgraph of a graph G, then any coloring of G produces a coloring of H as well. Since it may be possible to color H with even fewer colors, it follows that
Opposite to an independent set of vertices in a graph is a clique. A clique in a graph G is a complete subgraph of G. The order of the largest clique in a graph G is its clique number, which is denoted by ω(G). (The symbol ω is the Greek letter “omega.”) In fact,
In general, there is no formula for the chromatic number of a graph. In fact, determining the chromatic number of even a relatively small graph is often an extremely challenging problem. However, lower bounds for the chromatic number of a graph G can be given in terms of the clique number and the independence number and order of G.
Theorem 10.5 For every graph G of order n,
Proof. Let H be a clique of G having order ω(G). Then (H) = ω(G). Since H is a subgraph of G, it follows that (H) ≤ (G), that is, ω(G) ≤ (G).
Suppose that (G) = k. Then V(G) can be partitioned into k independent sets V1, V2, ..., Vk. Hence
Therefore, (G) = k ≥ n/ (G).
To establish sharpness for the bounds given in Theorem 10.5, consider the graph G = K3, 3, 3, 3 with
partite sets V1, V2, V3, V4, as illustrated in Figure 10.9. The order of G is n = 12, its independence numberis (G)=3anditscliquenumberisω(G)=4.Infact, (G)=4=ω(G)=n/ (G).A4-
coloring of G can be given by coloring the vertices in Vi with the color i for 1 ≤ i ≤ 4.
Figure 10.9: Coloring the graph K3, 3, 3, 3
I n Example 1.5 (in Chapter 1) we showed how a graph could model the traffic lanes at the intersection of two streets. We now revisit this example and consider a question that is relevant to this situation.
Example 10.6 Figure 10.10 shows the traffic lanes L1, L2, ..., L9 at the intersection of two busy streets. A traffic light is located at this intersection. During a certain phase of the traffic light, those cars in lanes for which the light is green may proceed safely through the intersection. What is the minimum number of phases needed for the traffic light so that (eventually) all cars may proceed through the intersection?
Figure 10.10: Traffic lanes at street intersections
Solution. Construct a graph G to model this situation (see Figure 10.10), where V(G) = {L1, L2, ..., L9} and two vertices (lanes) are joined by an edge if vehicles in these two lanes cannot safely enter the intersection at the same time, as there is a possibility of an accident.
Answering this question requires determining the chromatic number of the graph G in Figure 10.10. First notice that if S = {L2, L4, L6, L8}, then G[S] = K4 and so (G) ≥ 4. Since there exists a
4-coloring of G, as indicated in the graph of Figure 10.10, (G) = 4.
Since the vertex set of the graph G of Figure 10.10 can be partitioned quite obviously into the four independent sets {L1, L2, L3}, {L4, L5}, {L6, L7} and {L8, L9}, one might be led to say that the answer to the question in Example 10.6 is clearly 4. However, this observation (while also providing another 4-coloring of G) again only shows that (G) ≤ 4.
A coloring of a graph G can also be thought of as a function c from V(G) to the set N of positive integers (or natural numbers) such that adjacent vertices have distinct functional values, that is, a coloring of G is a function c : V(G) → N such that uv E(G) implies that c(u) ≠ c(v).
We now present an upper bound for the chromatic number of a graph in terms of its maximum degree. The technique used in the proof of the following result is algorithmic and Greedy in nature, in the sense that colors are assigned to the vertices, one vertex at a time, in what appears to be an optimal manner.
Theorem 10.7 For every graph G,
Proof. Let V(G) = {v1, v2, ..., vn}. Define a coloring c : V(G) → N recursively as follows: c(v1) = 1. Once c(vi) has been defined, 1 ≤ i ≤ n, define c(vi+1) as the smallest positive integer not already used to color any of the neighbors of vi+1. Since vi+1 has deg vi+1 neighbors, at least one of the integers 1, 2, ..., 1 + deg vi+1 is available for c(vi+1). Therefore, c(vi+1) ≤ 1 + deg vi+1. If the maximum color assigned to the vertices of G is c(vj), say, then
as desired.
Wehavealreadynotedthatifn≥3isodd,then (Cn)=3.Also, (Kn)=n.Hence (Cn)=1+
Δ(Cn) if n ≥ 3 is odd and (Kn) = 1 + Δ(Kn). Therefore, the bound presented in Theorem 10.7 is
attained for odd cycles and complete graphs. There is a theorem due to Rowland Leonard Brooks, which tells us that these are the only connected graphs for which the bound is attained. Since the proof is a bit involved, we do not include it.
Theorem 10.8 (Brooks’ Theorem) For every connected graph G that is not an odd cycle or a complete graph,
There is an upper bound for the chromatic number of a graph that is ordinarily superior to that given in Theorems 10.7 and 10.8 and which can be proved using an approach similar to that given for the proof of Theorem 10.7.
Theorem 10.9 For every graph G,
where the maximum is taken over all induced subgraphs H of G.
Proof. Among all induced subgraphs of G, let k denote the maximum of their minimum degrees.
SupposethatGhasordernandletvn beavertexofGn =GsuchthatdegG vn = (G).ThusdegG vn ≤ k. Therefore, Gn−1 = G − vn contains a vertex vn−1 such that . Continuing in this manner, we construct a sequence v1, v2, ..., vn of all vertices of G and a sequence G1, G2, ..., Gn ofinducedsubgraphsofGsuchthatvi V(Gi)for1≤i≤nand .
Define a coloring c : V(G) → N recursively as follows: c(v1) = 1. Once c(vi) has been defined, 1 ≤ i < n, define c(vi+1) as the smallest positive integer not already used to color any of the neighbors of vi+1. Since vi+1 has vi+1 neighbors among the vertices v1, v2, ..., vi and vi+1 ≤ k, at least one of the integers 1, 2, ..., k + 1 is available for c(vi+1). Hence every vertex of G is assignedoneofthecolors1,2,...,1+kandso (G)≤1+k,asdesired.
Let’s return to the inequality (G) ≥ ω(G) in Theorem 10.5. Although the lower bound ω(G) for (G) is attained when G = K3, 3, 3, 3 and, in fact, is attained for every complete multipartite graph, there
are numerous examples of graphs G for which (G) ≠ ω(G). For example, for G = C5, we have seen that (G) = 3;
Figure 10.11: The Grötzsch graph: A triangle-free graph with chromatic number 4
yet ω(G) = 2. The graph G of Figure 10.11 is known as the Grötzsch graph. This graph is triangle- free (it has no triangles) but has chromatic number 4. So (G) = 4 and ω(G) = 2.
It may seem that graphs with a large chromatic number must have large cliques, but this is not so. In fact, triangle-free graphs can have large chromatic numbers. This fact has been observed by a number of mathematicians. The following proof is due to Jan Mycielski, a mathematician who spent many years at the University of Colorado and who is known for his work in sets and logic. In the proof, we make use of a graph, sometimes called the shadow graph of a graph. The shadow graph S(G) of a graph G is obtained from G by adding, for each vertex v of G, a new vertex v′, called the shadow vertex of v, and joining v′ to the neighbors of v in G. Observe that (1) a vertex of G and its shadow vertex are not adjacent in S(G) and (2) no two shadow vertices are adjacent in S(G). The shadow graph S(C5) of C5 is shown in Figure 10.12. The Grötzsch graph of Figure 10.11 is then
obtained by adding a new vertex z to S(C5) and joining z to the shadow vertices in S(C5).
Figure 10.12: The shadow graph of C5
Theorem 10.10 For every integer k ≥ 3, there exists a triangle-free graph with chromatic
number k.
Proof. We proceed by induction on k. We have already seen that the result is true for k = 3 and k = 4. Assume that there is a triangle-free (k − 1)-chromatic graph F, where k ≥ 5 is an integer. Let G be the graph obtained by adding a new vertex z to the shadow graph S(F) of F and joining z to the shadow vertices in S(F). We show that G is a triangle-free graph with (G) = k.
First, we verify that G is triangle-free. Assume, to the contrary, that there is a set U of three vertices of G such that G[U] = K3. Since no two shadow vertices are adjacent in G, it follows that U
contains at most one shadow vertex. Because z is adjacent only to shadow vertices and U contains at least one vertex that is not a shadow vertex, z U. On the other hand, F is triangle-free and so at least one vertex of U is not in F. Therefore, U = {u, v, w′}, where u and v are adjacent vertices of F and w′ is a shadow vertex that is adjacent to u and v. Thus w ≠ u, v. However then, w is adjacent to u and v, producing a triangle in F, which is impossible since F is triangle-free.
It remains to show that (G) = k. Let c* be a (k − 1)-coloring of F. We extend c* to a k-coloring of G by defining c*(x′) = c*(x) for each x V(F) and defining c*(z) = k. Thus (G) ≤ k. Next we show that (G) ≥k. SinceF is a subgraph ofG, it follows thatk − 1 = (F) ≤ (G). Assume, to the contrary, that (G) = k − 1. Let there be given a (k − 1)-coloring c of G, say with colors 1, 2, ..., k − 1. We may assume that c(z) = k − 1. Since z is adjacent to every shadow vertex in G, it follows that the shadow vertices are colored with the colors 1, 2, ..., k − 2. For every shadow vertex x′ of G, the color c(x′) is different from the colors assigned to the neighbors of x. Therefore, if for each vertex y o f G belonging to F, the color c(y) is replaced by c(y′), we have a (k − 2)-coloring of F. This is impossible, however, since (F) = k − 1.
Theorem 10.10 therefore shows the existence of graphs G for which (G) is considerably larger
than ω(G). While there has been much interest in graphs G for which (G) > ω(G), there has even
been more interest in graphs G for which not only (G) = ω(G) but (H) = ω(H) for every induced
subgraph H of G. A graph G is called perfect if (H) = ω(H) for every induced subgraph H of G.
This concept was introduced in 1963 by the French mathematician Claude Berge. From our earlier
remarks, every complete multipartite graph is perfect and so every complete bipartite graph is
perfect. In fact, every bipartite graph is perfect (see Exercise 10.16).
Claude Berge made two conjectures concerning perfect graphs. The first of these was verified in
1972 by László Lovász and the second was verified in 2002 by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas.
The Perfect Graph Theorem A graph is perfect if and only if its complement is perfect.
The Strong Perfect Graph Theorem A graph G is perfect if and only if neither G nor contains
an induced odd cycle of length 5 or more.