Game of Mr Paint and Mrs Correct

In game theory, and in particular the study of positional games, the game of Mr Paint and Mrs Correct is a perfect information game that can be used in proofs of graph coloring and list coloring problems. It is due to graph theorist Uwe Schauz.
It is played on a given, fixed graph <math>G=(V,E)</math> as follows:
* (initialization). Mr Paint has many different colors, enough for each round of the game. In each round he uses a new color that cannot be used again. Mrs Correct has a finite stack <math>S_v</math> of erasers for each vertex <math>v\in V</math> of the game Graph G. The erasers lie at their corresponding vertices, ready for use.
* (1P). Mr Paint starts. He uses his first color to color a nonempty subset of V.
* (1C). Mrs Correct uses her erasers to clear newly coloured vertices. For each newly coloured vertex v, she may use one eraser from <math>S_v</math> to clear v, provided <math>S_v</math> is nonempty. An eraser may be used only once: after it is used, it is discarded. Mrs Correct's task is to avoid monochromatic edges (that is, edges with both vertices the same color).
* (2P). In the second round, Mr Paint uses his second color to colour a subset of the uncoloured vertices of G.
* (2C). Mrs Correct then uses up some of her erasers from stacks <math>S_v</math>, belonging to newly coloured vertices, to avoid monochromatic edges.
* (repeat).
* (end). The game ends when one player has no legal move, and that player loses. Mrs Correct cannot move if she cannot avoid monochromatic edges (because she does not have any erasers left at the relevant vertices), and Mr Paint loses if all vertices have already been coloured when it is his turn.
If Mrs Correct wins, the game results in a graph coloring of G. Schauz goes on to refine this game by giving Mr Paint only a single marker and allowing Mrs Correct to remove some edges.
A winning strategy for Mrs Correct is given by Schauz in 2010.

Main Menu

See Also

Main Menu