Deletion and palette size in the domatic number game

Abstract

Hartnell and Rall recently introduced the domatic number game. Alice and Bob color the vertices of a graph from a palette [\(k\)], and Alice wins if every color class is a dominating set at the end of the game. The largest winning palette size is denoted by \(\mathop{\mathrm{dom}}\nolimits_{g}(G)\) when Alice moves first and by \(\mathop{\mathrm{dom}}\nolimits'_{g}(G)\) when Bob moves first. Hartnell and Rall asked how these parameters behave under edge and vertex removal, and they also asked whether Bob can win with \(k\) colors while Alice wins with \(k+1\) colors. We give short answers. First, Alice-winning palettes are downward closed: if Alice can win with \(k+1\) colors, then she can win with \(k\) colors, in both versions of the game. Thus the proposed palette-size pathology never occurs. Second, if \(H\) is a spanning subgraph of \(G\), then \[ \mathop{\mathrm{dom}}\nolimits_{g}(H)\le \mathop{\mathrm{dom}}\nolimits_{g}(G),\qquad \mathop{\mathrm{dom}}\nolimits'_{g}(H)\le \mathop{\mathrm{dom}}\nolimits'_{g}(G). \] Thus edge deletion can never increase either invariant, and the inequalities may be strict. Finally, vertex deletion is not monotone: it can increase or decrease either invariant. Deleting one vertex can even increase either invariant by an arbitrarily large amount.