Map-coloring Games - Move Constraints

Move Constraints

An inherent constraint in each game is the set of colors available to the players in coloring regions. If Left and Right have the same colors available to them, the game is impartial; otherwise the game is partisan. The set of colors could also depend on the state of the game; for instance it could be required that the color used be different from the color used on the previous move.

The map-based constraints on a move are usually based on the region to be colored and its neighbors, whereas in the map-coloring problem, regions are considered to be neighbors when they meet along a boundary longer than a single point. The classical map-coloring problem requires that no two neighboring regions be given the same color. The classical move constraint enforces this by prohibiting coloring a region with the same color as one of its neighbor. The anticlassical constraint prohibits coloring a region with a color that differs from the color of one of its neighbors.

Another kind of constraint is entailment, in which each move after the first must color a neighbor of the region colored on the previous move. Anti-entailment is another possible constraint.

Other sorts of constraints are possible, such as requiring regions that are neighbors of neighbors to use different or identical colors. This concept can be considered as applying to regions at graph distance two, and can be generalized to greater distances.