Online Paintability: The Slow-Coloring Game

Abstract

The slow-coloring game is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the uncolored vertices, scoring $|M|$ points. Painter then gives a color to a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. Painter and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of $G$, written $\mathring{\mathrm{s}}(G)$. The game is an online variant of online sum list coloring. We proe $\frac{|V(G)|}{2\alpha (G)}+\frac{1}{2}\le \frac{\mathring{\mathrm{s}}(G)}{|V(G)|}\le \max \left\{\frac{|V(H)|}{\alpha (H)}:H\subset G\right\}$, where $\alpha (G)$ is the independence number, and we study when equality holds in the bounds. We compute $\mathring{\mathrm{s}}(G)$ for graphs with $\alpha (G)=2$. Among $n$-vertex graphs, we prove that $\mathring{\mathrm{s}}$ is minimized by the star and maximized by the path. We also obtain good bounds on $\mathring{\mathrm{s}}(K_{r,s})$.

18 pages. Revised introduction, restructured several proofs