Comment by karmakaze

The map coloring problem relates to graphs that are planar--can be drawn on a 2D surface without crossing edges. Graphs in general are not planar and so more than 4 colors may be necessary.