n 1853 Francis Guthrie hypothesized that you could color any map with only four colors so no two regions that share a common edge have the same color. It wasn’t until 123 years later in 1976 that Kenneth Appel and Wolfgang Haken proved that Guthrie was right. While the proof shows a method for finding four-colorings, it is enormous, examining 1,476 special cases of map arrangements. The proof is so big that large pieces of it are performed by a computer and no one has yet verified it by hand so some mathematicians refuse to admit that it is a “proper” proof.

In theory you could write a program to examine a map and use the 1,476 special cases to find a four-color solution, but the resulting program would be long, complicated, and impossibly hard to debug. It would probably also be fairly slow.

Despite the problems involved in writing a program to color a map in four colors, it’s not too difficult to write one that colors a map with five colors. Unless you have a strange monitor that can display only four colors at a time, five-coloring should be good enough for most applications.

Not Just For Maps
Map coloring algorithms are obviously useful for coloring maps but they have less obvious uses as well. For example, suppose your job is to assign frequencies to radio stations so that no stations near each other have the same frequency. You can treat this as a map coloring problem by making a node for each radio station, making links between those that are near each other, and then coloring the resulting graph. (Note that graph may require more than four or even five colors (frequencies) if many stations are very close to each other. In that case, the graph is non-planar.)

Similarly, in a class scheduling problem the goal is to schedule classes, ensuring instructors aren’t scheduled to teach two classes at the same time. You can model this problem by making a node for each class and connecting those that are taught by the same instructor. You can also add in links representing classes that must be taken by the same group of students (for example, suppose all freshmen must take Calculus 100, Physics 100, and Writing). The resulting graph coloring cal tell you the minimum number of time slots you need. (This graph may also be non-planar. For example, if one instructor teaches five classes, then you need at least five colors.)

Other less intuitive map-coloring problems involve circuit board short-circuit and feature testing, and register allocation. Keeping such other uses in mind, here’s how to write an algorithm to color a map using five colors.

From Maps to Graphs
The five-coloring algorithm relies on two key observations. I’ll describe the observations shortly but they are a bit easier to understand if you think in terms of graphs instead of maps.

You can represent any map as a planar graph (a graph where the links do not cross each other). Convert the regions into nodes in the graph. Connect two nodes with links if the two corresponding regions are adjacent.

Figure 1 shows a map on the left and the corresponding graph on the right. Node A on the right has links to nodes B, C, D, and E because in the map on the left region A has neighbors B, C, D, and E.

	?
Figure 1. Converting Maps to Graphs: You can convert any map into a planar graph.

In a graph, a node’s degree is the number of links that it has In Figure 1, node D has degree six because it has six links (and the corresponding region D in the map has six neighbors). A node’s neighbors are the nodes on the other ends of its links. In Figure 1, node D’s neighbors are nodes A, C, E, G, H, and I.

Thinking in terms of a graph, the five-coloring problem is to color each node in the graph so that no neighboring nodes have the same color.

Key Observations
The five-coloring algorithm uses two observations to convert a graph into a simpler graph that has the same color properties as the original. It then five-colors the simpler graph and uses the result to color the original more complicated graph. This will be easier to understand when you see an example.

The first observation is that you can easily assign a color to a node N that has degree less than five. If the node has fewer than five neighbors, those neighbors cannot use up all five of the available colors so at least one color remains for node N.

	?
Figure 2. Simplifying Coloring: The figure illustrates Rule 1 for simplifying a graph and applying colors.

This leads to Rule 1 for simplifying the graph: For each node N with degree less than five, remove it from the graph, five-color the remaining graph, restore node N, and pick a color for it from the colors that are not used by its neighbors.

Figure 2 shows an example graphically. In the original graph on the left, node A has only two neighbors: B and C. Remove node A to get the second graph. Use your five colors to color the smaller graph (the third picture in Figure 2 where B and C are colored blue and yellow). Finally restore node A and give it a color that is not used by B or C (the last picture in Figure 2).

For many graphs, Rule 1 suffices to produce a valid five-coloring. The logic translates to a programming loop: While the graph contains a node, find a node with degree less than five and remove it. Continue removing nodes until the graph is empty. Then start adding the nodes back into the graph in reverse order, assigning each node colors that are not used by its neighbors.

	?
Figure 3. Too Many Neighbors: In some maps and graphs, every region or node has at least five neighbors, so Rule 1 won’t work.

This method works as long you can always find a node with fewer than five neighbors. For example, you can five-color the graphs shown in Figure 1 and Figure 2 in this way.

However, if every node has at least five neighbors, then Rule 1 doesn’t work. Figure 3 shows a map and corresponding graph where every node has five neighbors. Because every node has degree five, you cannot use Rule 1 to simplify it.

To simplify this graph, you need to make a second more complicated observation. It can be shown (although not by me) that, if a graph contains no nodes with degree less than five, then you can find at least one node X with neighbors N1 and N2 where:

• X has exactly five neighbors
• N1 and N2 have at most seven neighbors
• N1 and N2 are not neighbors of each other

	?
Figure 4. Simplifying Graphs: The figure illustrates Rule 2 for simplifying a graph.

Now suppose we require that nodes N1 and N2 have the same color. Because they are not neighbors of each other, that is possible. Then because node X has exactly five neighbors and two of them (N1 and N2) are using the same color, we know that node X’s neighbors have not used all five colors?so you can assign one of the unused colors to node X.

This leads to Rule 2 for simplifying the graph: If the graph contains no nodes with degree less than five, find nodes X, N1, and N2 as described previously and remove all three from the graph. Create a new node N1/N2 to represent the color that nodes N1 and N2 should have and give it the same neighbors that nodes N1 and N2 had.

The resulting graph has two fewer nodes than the original. It also has fewer links because you removed the five links to node X, and the new node (N1/N2) has no more links than nodes N1 and N2 did. (It may contain fewer if N1 and N2 had common neighbors.)

Figure 4 shows the graph from Figure 3 after applying Rule 2. In this example, the roles of X, N1, and N2 were played by nodes A, F, and C respectively. I removed nodes A, F, and C, created a new node F/C, and gave it the same links that nodes F and C had.

In Figure 4, nodes B and E have degree less than five so Rule 1 applies. Removing those nodes simplifies other nodes so Rule 1 is enough to finish the job.)

	?
Figure 5. Applying Coloring Rules: Here’s an illustration of the complete algorithm for five-coloring the graph in Figure 3, using both Rules 1 and 2.

After applying Rule 2, you can continue applying the rules to simplify the graph further. Often, (as in this case) applying Rule 2 makes the graph simple enough that you can apply Rule 1 again. Again, you proceed using Rules 1 and 2 until the graph is empty, after which you start adding nodes back into it as before. When you are ready to restore nodes X, N1, and N2, you first remove the artificial node N1/N2. Give N1 and N2 whatever color you assigned to node N1/N2 in the simpler graph. Restore node X and pick a color for it that isn’t used by its neighbors.

Figure 5 shows the entire process for the graph shown in Figure 3. Follow the arrows to see how the graph is pulled apart with Rules 1 and 2, and then put back together again in the reverse order. As the graph is dismantled, the nodes that will be removed in the following step are highlighted with blue circles. As the graph is rebuilt, the newly added nodes at each step are highlighted similarly.

It is important to note that Rule 1 and Rule 2 both reduce the number of nodes in the graph. That means the graph will eventually run out of nodes, so the process will complete. In other words, the rules prevent an algorithm from simply rearranging the nodes and running forever, reshuffling the nodes but not making any progress. Because both rules remove at least one node from the graph, the process can take at most N steps where N is the number of nodes in the original graph.

Writing Colorful Code
The downloadable example program for this article is rather involved and contains a lot of code that isn’t related to map coloring so I haven’t shown it all here. For example, it includes a simple map editor (not discussed) that lets you draw regions to color.

The program represents regions on the map with the MapRegion class. This class provides basic support for adding and removing a region from a list of MapRegion objects.

The code in Listing 1 shows the most important parts of the main program’s map-coloring code. I’ve used VB.NET for the code in this article, but the download includes a C# version.

The code begins by declaring a list called m_Regions that holds the MapRegions that comprise the map: Private

   m_Regions As New List(Of MapRegion)

It then declares a RuleTypes enumeration that defines values representing the two rules for simplifying the map.

   ' The two rules for simplifying the map.   Private Enum RuleTypes       DegreeUnderFive       NonAdjacentNeighbors   End Enum

The AssignColors method controls the map coloring process. It creates a stack named action_stack to keep track of the rules the program follows and the objects that are involved when the map is manipulated.

   Private Sub AssignColors()       ' The removed regions.       Dim action_stack As New Stack()          ' Simplify the map.       Do While m_Regions.Count > 0           SimplifyMap(m_Regions, action_stack)       Loop          ' Rebuild the map.       Do While action_stack.Count > 0           RestoreRegion(m_Regions, action_stack)       Loop   End Sub

While the m_Regions collection holds any MapRegion objects, AssignColors calls the SimplifyMap method (see Listing 1) which appliesthe two rules. It continues calling SimplifyMap until m_Regions is empty.

Next the subroutine calls RestoreRegion to undo one of the rules stored in action_stack. It continues calling RestoreRegion until the stack is empty and all of the MapRegion objects have been restored to the map and colored properly.

Subroutine SimplifyMap first attempts to apply Rule 1, searching the regions list for a region with a degree less than five. If it finds such a region, it removes it from the regions list and adds it to the stack. It also adds the RuleTypes value DegreeUnderFive to the stack to remember that it used Rule 1 on this node.

If SimplifyMap cannot apply Rule 1, it applies Rule 2, searching for a region with a degree of exactly five that has neighbors N1 and N2 that are not neighbors of each other. The MapRegion class’s FindNonAdjacents function returns True when a region satisfies these conditions.

After finding the necessary node and its neighbors, the subroutine removes the node. It makes a new node to represent the neighbors, makes the new node adopt the neighbors’ lists of neighbors, and adds the new node to the regions list. It then removes the original neighbors from the list and pushes all the relevant objects onto the stack. It finishes by adding the RuleTypes value NonAdjacentNeighborsto the stack to record the fact that it used Rule 2 on these objects.

Subroutine RestoreRegion reverses the most recent simplification. It pops the most recent RuleTypes value off the stack to determine which rule was used at this point in the simplification process.

If the most recent simplification was made with Rule 1, the subroutine pops the node that was removed under Rule 1 off the stack. It puts the node back in the map and calls its AssignColor method to give it a color. The MapRegion class’s AssignColor method picks a color for the node that isn’t used by its neighbors. Because the region has degree less than five, there is at least one unused color available.

   ' Assign a color to this region.   Public Sub AssignColor()      Me.ColorIndex = 0         ' Try each color (skipping the "unassigned" color).      For test_color As Integer = 1 To BackColor.Length - 1         ' See if neighbor is using this color.         Dim is_used As Boolean = False         For Each nbr As MapRegion In Neighbors            If nbr.ColorIndex = test_color Then               is_used = True               Exit For            End If         Next nbr            ' See if the color is available.         If Not is_used Then            Me.ColorIndex = test_color            Exit For         End If      Next test_color         ' Make sure we found a color.      Debug.Assert(Me.ColorIndex > 0, _         "Error assigning a color to the region")   End Sub

If instead the most recent simplification was made with Rule 2, the subroutine pops all the relevant objects off the stack. It restores the neighbors to the map and sets their colors to the color previously assigned to the combined region. It then removes the combined region, restores the original node X that had degree exactly five, and calls its AssignColor method.

As you can see, coloring a map with five colors isn’t too hard. In fact, because the MapRegion class’s AssignColor method considers the five available colors in the same order every time, it picks the fifth color only when it must?so it often finds four-colorings “accidentally.” However, if you really need to produce four-color maps reliably every time, you can always check the 1,476 special cases used in Appel and Haken’s proof!