RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


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.

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.

Author's Note: You can learn more about the four-color theorem from Wikipedia and Wolfram MathWorld.

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.

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date