The Complexity of Flood Filling Games by Clifford, Jalsenius, Monanaro, Sach Shows for the actualy grid version:

(1) c GE 3 then flood-it and free-flood-it are NP-hard,

(2) 3xn, unbounded numb of colors, flood-it and free-flood-it are NP-hard,

(3) 2xn, ubded colors, flood-it is in P (OPEN in this paper: free-flood-it)

(4) c=2 then free-flood-it is in P,

(5) there is a (c-1)-approx and a randomized 2c/3-approx.

(6) no constant-approx.

(7) Number of moves needed in the worst case is Omega(sqrt(c)n)

(8) For a random board, cge 2, requires Omega(n).

2-Free-Flood-it is polynomial by Lagoutte

For free-flood-it on graphs, c=2, in Poly time.

The Complexity of Free-Flood-It on 2xn boards by Meek and Scott

When restricted to 2xn, free-flood-it FPT with c as parameter.

An Algorithmic analysis of flood-it and free-flood-it on graph powers by Souza, Protti, Silva

Flood-it on AT-free graphs by Hon, Kloks, Liu, Liu, Wang

How bad is the freedom to flood-it? by Belmonte, Ghadikolaei, Kiyomi, Lampis, Otachi

Extremal properties of flood-filling games by Meeks and Vu

Looks at which graphs give the worst number of moves needed.

Parameterized complexity of flood-filling games on trees by Souza, Protti, da Silva

(1) Flood-it is NP-hard even on trees where all leaves are LE 2 from root.

(2) Flood-it is equiv to Restricted Shortest Common Subsequence.

Tractability and hardness of flood filling games on trees by Fellows, Souza, Protti,da Silva

(1) Flood-it is equiv to Restricted Shortest Common Subsequence.

(2) 3-color tree versions of flood-it and free-flood-it are NP-hard.

A Survey on the Complexity of Flood-Filling Games by Fellows, Protti, Rosamond, da Silva, Souza

The Complexity of Some Problems on Subsequences and Supersequences by Maier

The Shortest Common Supersequence Problem over a binary alphabet is NPC by Raiha and Ukkonen]