Skip to main content
1 of 3

Necessary Conditions for a Graph not possible to Rainbow Color?

Suppose we have a $t$-uniform hypergraph ($t \ge 3$) $G$, and have $v \ge 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 $v = 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 a sufficient condition for when $v = t+1$, or of all necessary conditions even when $v = t = 3$.

Has this problem been studied before?