0
$\begingroup$

Suppose we have a $t$-uniform hypergraph ($t \ge 3$) $G$, and have $t$ colors available. A question in my research is equivalent to asking what the necessary and sufficient conditions are on $G$ for which no possible vertex coloring of $G$ has every edge rainbow colored. As long as there exists some edge that is not rainbow for every possible coloring of $G$, that's enough.

A sufficient condition I've determined is if $t$ and $G$ contains 3 distinct edges $E_1, E_2, E_3$ for which $|E_1 \cap E_2| \ge t/2$ and $E_3$ contains the symmetric difference of $E_1, E_2$, it is not possible to have all $E_1, E_2, E_3$ be rainbow, and the argument is simple. However, this is not a necessary condition, as other examples of $G$ can be formed. I don't even know of all necessary conditions even when $t = 3$.

Has this problem been studied before?

Edit: for $t=3$, an infinite class of $G$'s can be formed: let $k \ge 1$ be any integer, and take $3k+2$ edges $E_1, \cdots, E_{3k+2}$ such that $|E_i \cap E_{i+1}| = 2$ for all $i$ (so a "maximally overlapping path"), and then a final edge $F$ such that $F$ contains the first vertex of $E_1$ and the "last" vertex of $E_{3k+2}$. The choice of $3k+2$ enforces that the same color appears in these two vertices. Then all of $E_1, \cdots, E_{3k+2}, F$ cannot be simultaneously rainbow. Is this the only family of $G$'s for $t=3$?

Edit 2: @user36212 rightfully showed that the problem is NP-hard for a number of colors larger than $t$, so I've updated the question for when they are the same.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ This problem is well known to be NP-hard (see the book by Garey and Johnson, or simply use the obvious reduction to graph colouring for v>t). So you should expect that no simple necessary and sufficient conditions exist. $\endgroup$
    – user36212
    Commented Feb 26, 2019 at 14:01
  • $\begingroup$ @user36212 I think you're doing the reduction in the wrong direction. And the "NP-hard" type question here would be to find a maximum size subgraph without an induced copy of $G$. For $t=2$, this turns out to be equivalent to the Max 2-SAT problem, but the condition for $G$ to be avoided is easy to state. $\endgroup$
    – Ryan Dougherty
    Commented Feb 26, 2019 at 15:15
  • $\begingroup$ For t=2,v=3 your problem is exactly graph-3-colouring, right? And now to go up in uniformity from this, for general t and v=t+1 take a 2-graph G, add t-2 vertices, and put t-edges containing all the new vertices plus each edge of G. To rainbow colour the resulting graph with v colours, you need to use one colour per new vertex and then G must be 3-colourable, so your problem is NP-hard for v=t+1 and this generalises easily for fixed v>t. $\endgroup$
    – user36212
    Commented Feb 26, 2019 at 19:09
  • $\begingroup$ @user36212 I see, thank you for explicitly giving the reduction! This does indeed show hardness for $v > t$. $\endgroup$
    – Ryan Dougherty
    Commented Feb 26, 2019 at 20:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .