Graph Coloring
Each map in the plane can be represented by a graph. Each region of the map is represented by a vertex. Edges connect two vertices if they have a common border. This is called the dual graph of the map.
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.
The chromatic number of a graph is the least number of colors needed for a coloring of this graph.
The four color theorem states that every planar graph can be colored using four or fewer colors.