## 5.5 Graph Coloring The *m*-Coloring problem concerns finding all ways to color an undirected graph using at most *m* different colors, so that no two adjacent vertices are the same color. We usually call the *m*-Coloring problem a unique problem for each value of *m.* Example 5.5****Consider the graph in [Figure 5.10](#ch05fig10). There is no solution to the 2-Coloring problem for this graph because, if we can use at most two different colors, there is no way to color the vertices so that no adjacent vertices are the same color. One solution to the 3-Coloring problem for this graph is as follows: *Vertex* *Color* *v*1 color 1 *v*2 color 2 *v*3 color 3 *v*4 color 2 [](fig5-10_0.jpg) Figure 5.10: Graph for which there is no solution to the 2-Coloring problem. A solution to the 3-Coloring problem for this graph is shown in [Example 5.5](#ch05ex09). There are a total of six solutions to the 3-Coloring problem for this graph. However, the six solutions are only different in the way the colors are permuted. For example, another solution is to color *v*1 color 2, *v*2 and *v*4 color 1, and *v*3 color 3. **** An important application of graph coloring is the coloring of maps. A graph is called ***planar*** if it can be drawn in a plane in such a way that no two edges cross each other. The graph at the bottom of [Figure 5.11](#ch05fig11) is planar. However, if we were to add the edges (*v*1, *v*5) and (*v*2, *v*4) it would no longer be planar. To every map there corresponds a planar graph. Each region in the map is represented by a vertex. If one region is adjacent to another region, we join their corresponding vertices by an edge. [Figure 5.11](#ch05fig11) shows a map at the top and its planar graph representation at the bottom. The *m*-Coloring problem for planar graphs is to determine how many ways the map can be colored, using at most *m* colors, so that no two adjacent regions are the same color. [](fig5-11_0.jpg) Figure 5.11: Map (top) and its planar graph representation (bottom). A straightforward state space tree for the *m*-Coloring problem is one in which each possible color is tried for vertex *v*1 at level 1, each possible color is tried for vertex *v*2 at level 2, and so on until each possible color has been tried for vertex *vn* at level *n*. Each path from the root to a leaf is a candidate solution. We check whether a candidate solution is a solution by determining whether any two adjacent vertices are the same color. To avoid confusion, remember in the following discussion that "node" refers to a node in the state space tree and "vertex" refers to a vertex in the graph being colored. We can backtrack in this problem because a node is nonpromising if a vertex that is adjacent to the vertex being colored at the node has already been colored the color that is being used at the node. [Figure 5.12](#ch05fig12) shows a portion of the pruned state space tree that results when this backtracking strategy is applied to a 3-coloring of the graph in [Figure 5.10](#ch05fig10). The number in a node is the number of the color used on the vertex being colored at the node. The first solution is found at the shaded node. Nonpromising nodes are labeled with crosses. After *v*1 is colored color 1, choosing color 1 for *v*2 is nonpromising because *v*1 is adjacent to *v*2. Similarly, after *v*1, *v*2, and *v*3 have been colored colors 1, 2, and 3, respectively, choosing color 1 for *v*4 is nonpromising because *v*1 is adjacent to *v*4. [](fig5-12_0.jpg) Figure 5.12: A portion of the pruned state space tree produced using backtracking to do a 3-coloring of the graph in [Figure 5.10](#ch05fig10). The first solution is found at the shaded node. Each nonpromising node is marked with a cross. Next we present an algorithm that solves the *m*-Coloring problem for all values of *m*. In this algorithm the graph is represented by an adjacency matrix, as was done in [Section 4.1](LiB0033.html#366). However, because the graph is unsheathed, eachentry in the matrix is simply true or false depending on whether or not there is an edge between the two vertices. Algorithm 5.5: The Backtracking Algorithm for the, m-Coloring Problem****Problem: Determine all ways in which the vertices in an undirected graph can be colored, using only *m* colors, so that adjacent vertices are not the same color. Inputs: positive integers *n* and *m*, and an undirected graph containing *n* vertices. The graph is represented by a two-dimensional array *W*, which has both its rows and columns indexed from 1 to *n*, where *W \[i\] \[j\]* is true if there is an edge between *i*th vertex and the *j*th vertex and false otherwise. Outputs: all possible colorings of the graph, using at most *m* colors, so that no two adjacent vertices are the same color. The output for each coloring is an array *vcolor* indexed from 1 to *n*, where *vcolor \[i\]* is the color (an integer between 1 and *m*) assigned to the *i*th vertex. ``` void m_coloring (index i) { int color; if (promising (i)) if (i == n) cout << vcolor [1] through vcolor [n]; else for (color = 1; color <= m; color++){ // Try every vcolor [i + 1] = color; // color for m_coloring (i + 1); // next vertex. } } bool promising (index i) { index j; bool switch; switch = true; j = 1; while (j && switch){ // Check if an if (W[i][j] && vcolor[i] == vcolor[j]) // adjacent vertex switch = false; // is already j++; // this color. } return switch; } ``` **** Following our usual convention, *n*, *m*, *W*, and *vcolor* are not inputs to either routine. In an implementation of the algorithm, the routines would be defined locally in a simple procedure that had *n*, *m*, and *W* as inputs, and *vcolor* defined locally. The top level call to *m*\_coloring would be  The number of nodes in the state space tree for this algorithm is equal to  This equality is obtained in [Example A.4](LiB0095.html#1299) in [Appendix A](LiB0093.html#1281). For a given *m* and *n*, it is possible to create an instance that checks at least an exponentially large number of nodes (in terms of *n*). For example, if *m* is only 2, and we take a graph in which *vn* has an edge to every other node, and the only other edge is one between *v**n*–2 and *v**n*–1, then no solution exists, but almost every node in the state space tree will be visited to determine this. As with any backtracking algorithm, the algorithm can be efficient for a particular large instance. The Monte Carlo technique described in [Section 5.3](LiB0041.html#500) is applicable to this algorithm, which means that it can be used to estimate the efficiency for a particular instance. In the exercises, you are asked to solve the 2-Coloring problem with an algorithm whose worst-case time complexity is not exponential in *n*. For *m* ≥ 3, no one has ever developed an algorithm that is efficient in the worst case. Like the Sum-of-Subsets problem and the 0–1 Knapsack problem, the *m*-Coloring problem for *m* ≥ 3 is in the class of problems discussed in [Chapter 9](LiB0074.html#880). This is the case even if we are looking for only one *m*-coloring of the graph.