Number of moves to solve a flood-it/sock-dye game

Well, it's easy to say something about the case $c=2$. There is no strategy, since all you can do is alternate between the two colors. Since there is a path of length $2n-2$ (counting the edges) between any two points, no game can take more than $2n-2$ moves. It's easy to construct a game that takes $2n-2$ moves; just use a checkerboard coloring.

At the other extreme, it's easy to say something about the case $c=n^2$. If each node is a different color, then you can always extend by one node at each move, and you can never extend by more than one node, so an optimal strategy will take $n^2-1$ moves.

So now we just have to fill in all the cases in between....