Is k -rainbow coloring of a hypergraph NP-complete or not?

Question

**A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Is k-rainbow coloring of a hypergraph is NP-complete or not? The problem is also called "polychromatic coloring" **

I looked at some reference papers such as "Hardness of Rainbow Coloring Hypergraphs by Venkatesan Guruswami and Rishi Sakety" and "Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs by Venkatesan Guruswami and Euiwoong Lee". But these are the only reference I found discuss the problem but the authors foucs on generating balance rainbow coloring for K-uniform hypergraph where each color has to appear the same number of times in the hypergraph. It has been proved that K-rainbow coloring for planer graph is P for K= 2 and NP complete for K=3,4 according to this reference "Polychromatic Colorings of Plane Graphs".

My question " Is k-rainbow coloring of a hypergraph NP-complete or not?" in general for any hypergraph. I think this problem is related to vertex cover problem.

Answer 1

Deciding if a hypergraph can be rainbow colored in $k$ colors is NP-complete for every $k \geq 2$. A proof is given in [1, Theorem 12].

For $k=2$, the result follows immediately by observing the problem is equivalent to set splitting (also known as hypergraph 2-coloring). For $k \geq 3$, the authors of [1] give a reduction from chromatic index on $k$-regular graphs.

---

[1] M. Koivisto, P. Laakkonen, and J. Lauri. "NP-completeness results for partitioning a graph into total dominating sets". In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON), volume 10392 of Lecture Notes in Computer Science, pages 333-345. Springer, 2017.