We'd like to take a map consisting of a set of non-overlapping regions and ``color'' it (assign a color to each region) so that no two contiguous regions have the same color. Want to minimize the number of colors.
Important in scheduling problems.
What's the natural decision problem?
