Minimum number of moves in this Graph Coloring "Game" You're given a graph $G = (V, E)$ and a set of colors $C = \{c_1, \cdots, c_v\}$, and the task is as follows:


Color the vertices using the colors in $C$.
Remove any edges that have differing colors for its endpoints (of course, if a vertex eventually has all edges removed, it can be deleted - but it is not necessary).
Repeat the above two steps until there are no edges left in the graph.


Suppose that $k = |V|$ is the number of vertices, $m = |E|$ is the number of edges, and $v = |C|$ is the number of colors. I am interested in the quantity $p(k, m, v)$, which is the smallest number of iterations of the above algorithm given $k, m, v$. Of course, we need $v \ge 2$ (couldn't remove any edges otherwise), and $p(k, m, v) \le m$ because we can color one edge at a time. We can also denote this quantity by $p(G, v)$. 

Based on a combinatorial object that is equivalent with respect to this procedure (perfect hash families), when we have the complete graph $K_k$, one can prove that $p(K_k, v) = \lceil \log_v(k) \rceil$. So of course $p(k, m, v) \le \lceil \log_v(k) \rceil$ if $G$ is a simple graph.

But the more interesting case is when we have $G$ be a hypergraph. Here, we remove hyperedges that are rainbow (i.e., every vertex in the hyperedge is a distinct color). Based on PHFs, there are lower and upper bounds for $p(G, v)$ when $G$ is the complete $t$-uniform hypergraph. In general, $p(G, v) \in \Theta(\log k)$ for these graphs, but the hidden constant heavily depends on $v, t$.

Are there references that have looked at a similar problem for hypergraphs?
The value of $p(G,v)$ is at most $r$ if you can label the vertices of $G$ with colors from $[v]^r$ in such a way that the colors assigned to every pair of adjacent vertices differ on at least one coordinate. Equivalently, $p(G,v) \leq r$ if you can label the vertices of $G$ with colors from $[v]^r$ in such a way that every pair of adjacent vertices gets a different color. Stated differently, $p(G,v) \leq r$ iff $\chi(G) \leq v^r$, where $\chi(G)$ is the chromatic number of $G$. This implies the formula
$$ p(G,v) = \lceil \log_v \chi(G) \rceil. $$
A similar relation should hold for the case of hypergraphs if you use the correct definition of chromatic number.