Col
A vertex-colouring game on graphs where players cannot play adjacent to their own colour.
Rules
Board. An undirected simple graph (no loops or multiedges). Each vertex may be either uncoloured or else coloured blue or red (but not both).
Left moves. Pick an uncoloured vertex that is not adjacent to any blue vertices, and colour it blue.
Right moves. Pick an uncoloured vertex that is not adjacent to any red vertices, and colour it red.
Convention. Classical (normal or misère play).
Notes
This is a short partizan ruleset. It is partizan because only Left can colour a vertex blue (and only Right can colour a vertex red). To see why it is short, consider the following:
- finite: the initial graph is finite, and each vertex is in one of three states (uncoloured, blue, or red), so the number of subpositions is always finite.
- loop-free: since an uncoloured vertex gets coloured after each move, the number of uncoloured vertices is reduced by 1 each turn. (So, in fact, the birthday of a position is bounded above by the number of uncoloured vertices.)