Extremal properties of flood-filling games
From MaRDI portal
Publication:5226850
zbMATH Open1417.05128arXiv1504.00596MaRDI QIDQ5226850FDOQ5226850
Authors: Kitty Meeks, Dominik K. Vu 
Publication date: 1 August 2019
Abstract: 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 several upper and lower bounds on this quantity for arbitrary graphs and show that all of the bounds are tight for trees; we also investigate how much the upper bounds can be improved if we restrict our attention to graphs with higher edge-density.
Full work available at URL: https://arxiv.org/abs/1504.00596
Recommendations
Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)
Cited In (8)
- On complexity of flooding games on graphs with interval representations
- Algorithms and Computation
- A Survey on the Complexity of Flood-Filling Games
- How Bad is the Freedom to Flood-It?
- The complexity of flood-filling games on graphs
- Spanning trees and the complexity of flood-filling games
- The complexity of flood filling games
- Flooding games on graphs
This page was built for publication: Extremal properties of flood-filling games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226850)
