**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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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