Mr. Paint and Mrs. Correct

Abstract

We introduce a coloring game on graphs, in which each vertex $v$ of a graph $G$ owns a stack of $\ell_v{-}1$ erasers. In each round of this game the first player Mr. Paint takes an unused color, and colors some of the uncolored vertices. He might color adjacent vertices with this color – something which is considered "incorrect". However, Mrs. Correct is positioned next to him, and corrects his incorrect coloring, i.e., she uses up some of the erasers – while stocks (stacks) last – to partially undo his assignment of the new color. If she has a winning strategy, i.e., she is able to enforce a correct and complete final graph coloring, then we say that $G$ is $\ell$-paintable.

Our game provides an adequate game-theoretic approach to list coloring problems. The new concept is actually more general than the common setting with lists of available colors. It could have applications in time scheduling, when the available time slots are not known in advance. We give an example that shows that the two notions are not equivalent; $\ell$-paintability is stronger than $\ell$-list colorability. Nevertheless, many deep theorems about list colorability remain true in the context of paintability. We demonstrate this fact by proving strengthened versions of classical list coloring theorems. Among the obtained extensions are paintability versions of Thomassen's, Galvin's and Shannon's Theorems.