Previous | ToC | Next Labs: Graph Theory. Part 2. Math Alive

Map Coloring

Suppose you are given a map on which the borders are marked between different countries or states, and asked to color the map, using as few colors as possible (to limit printing costs), with the extra restriction that countries sharing a border always have different colors (so that borders can be seen clearly). This map coloring problem is really a graph coloring problem in disguise: just represent every country by a vertex of a graph, and connect two vertices with an edge if the corresponding countries have a common border.

You can practice coloring the map of Blockvotia below:

Is it possible to color this map in three colors? Can you explain why?

Previous | ToC | Next Last Modified: November 2008