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?

  • $\begingroup$ 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. $\endgroup$ – rus9384 Oct 6 '17 at 23:05
  • $\begingroup$ @rus9384 Right, but one can do better by coloring in such a way to remove many of edges in one iteration. $\endgroup$ – Ryan Oct 6 '17 at 23:06
  • $\begingroup$ If you are looking for optimal algorithm time complexity, $\Theta(m)$ it is. $\endgroup$ – rus9384 Oct 6 '17 at 23:07
  • $\begingroup$ 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? $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.