# 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?

• But you can just take any edge, color it's ends with different colors and remove it. Since recoloring is allowed, the number of moves is $m$ and the same should be the complexity. – rus9384 Oct 6 '17 at 23:05
• @rus9384 Right, but one can do better by coloring in such a way to remove many of edges in one iteration. – Ryan Oct 6 '17 at 23:06
• If you are looking for optimal algorithm time complexity, $\Theta(m)$ it is. – rus9384 Oct 6 '17 at 23:07
• It's not clear what you mean by $p(k,m,v)$. Is is the minimum of $p(G,v)$ over all graphs having $k$ vertices and $m$ edges? – Yuval Filmus Oct 7 '17 at 10:26

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.