TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
 Specialized Dev Zones Research Center eBook Library .NET Java C++ Web Dev Architecture Database Security Open Source Enterprise Mobile Special Reports 10-Minute Solutions DevXtra Blogs Slideshow

# Colorful Algorithms: Solving Map-coloring and Related Problems

## It has been proven that you can always color a map with four colors in such as way that no two adjacent regions have the same color. Unfortunately doing so can be both difficult and time consuming—but it's not too hard to color a map with five colors.

 by Rod Stephens
 Oct 27, 2006
 Page 1 of 3

### WEBINAR:On-Demand

Building the Right Environment to Support AI, Machine Learning and Deep Learning

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.