Flood-It with Jewelry -- Characterizing the Game Complexity for Cograph Generalizations (opens in new tab)

Flood-It is a single-player game played on a precolored graph $G$, where the objective is to make $G$ monochromatic using as few flooding moves as possible. In each move, a color $c$ is selected and all vertices reachable from a fixed pivot vertex via a monochromatic path are recolored with $c$. In the free variant, the pivot may be chosen anew in every move. Deciding whether a graph can be made monochromatic in at most $k$ moves is NP-complet...