# Necessary Conditions for a Graph not possible to Rainbow Color?

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.

• 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. – user36212 Feb 26 at 14:01
• @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. – Ryan Feb 26 at 15:15
• 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. – user36212 Feb 26 at 19:09
• @user36212 I see, thank you for explicitly giving the reduction! This does indeed show hardness for $v > t$. – Ryan Feb 26 at 20:05