Extremal properties of flood-filling games

Kitty Meeks, Dominik K. Vu

Published 2015-04-02, updated 2015-04-15Version 2

The problem of determining the number of "flooding operations" required to make a given coloured graph monochromatic in the one-player combinatorial game Flood-It has been studied extensively from an algorithmic point of view, but basic questions about the maximum number of moves that might be required in the worst case remain unanswered. We begin a systematic investigation of such questions, with the goal of determining, for a given graph, the maximum number of moves that may be required, taken over all possible colourings. We give two upper bounds on this quantity for arbitrary graphs, which we show to be tight for particular classes of graphs, and determine this maximum number of moves exactly when the underlying graph is a path, cycle, or a blow-up of a path or cycle.