Map-coloring Games

Map-coloring Games

Several map-coloring games are studied in combinatorial game theory. The general idea is that we are given a map with regions drawn in but with not all the regions colored. Two players, Left and Right, take turns coloring in one uncolored region per turn, subject to various constraints. The move constraints and the winning condition are features of the particular game.

Some players find it easier to color vertices of the dual graph, as in the Four color theorem. In this method of play, the regions are represented by small circles, and the circles for neighboring regions are linked by line segments or curves. The advantages of this method are that only a small area need be marked on a turn, and that the representation usually takes up less space on the paper or screen. The first advantage is less important when playing with a computer interface instead of pencil and paper. It is also possible to play with Go stones or Checkers.