The four-color theorem

The other day Ran has told me an interesting problem: the four color theorem.
This is a theorem, which states that given any plane separated into regions, such as a political map of the states of a country, the regions may be colored using no more than four colors in such a way that no two adjacent regions receive the same color.
The conjecture was first proposed in 1852 when Francis Guthrie, while trying to color the map of counties of England, noticed that only four different colors were needed (Wikipedia).
The proof was given by N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas in 1996. It can be found at: http://www.ams.org/era/1996-02-01/S1079-6762-96-00003-0/S1079-6762-96-00003-0.pdf
It can be interesting to think how many colours do we need in n-dimension where n>2.
Shlomo, thanks for the refinement.