According to the four color map theorem it requires no more than four colors to fill in any map while making sure that no adjacent areas share the same color.
Working off a similar principle is the newest release announced by Gamewright. In Rolling America, each player attempts to fill a map of the United States with the numbers rolled on a set of colored dice. The challenge, though, is that the numbers in adjacent states may not differ by more than one. Any time a player finds it impossible to write a die’s number in a state with a matching color, they must instead fill one of those states with an “X”. At the end of the game, the player with the fewest Xs is the winner.
Rolling America is based on a similar game previously released in Japan and is scheduled to hit retail this fall at a suggested price of $11.