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
October 27, 2006
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.
It's quick, easy and you get access to all the articles on DevX.
This registration/login is to allow you to read articles on devx.com. Already a member?
To become a member of DevX.com create your Member Profile by completing the form below. Membership is free!
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.
