# Complexity of K-Colorful Coloring Problem for a Hypergraph

I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem let me know. I think it will be NP-Complete

Let H = (V, E) be a hypergraph, and let ϕ be a coloring of H. A hyperedge e ∈ E is said to be k-colorful with respect to ϕ if there exist k vertices in e that are colored distinctively under ϕ. The coloring ϕ is called k-colorful if every hyperedge e ∈ E is min{|e|, k}-colorful. Let $$c_H (k)$$ denote the least integer $$L$$ such that H admits a k-colorful coloring with $$L$$ colors.

The reference for the problem is E.Horev, R.Krakovski, and S.Smorodinsky, “Conflict-free color-ing made stronger,” in Scandinavian Workshop on Algorithm Theory,pp. 105–117, Springer, 2010.

A strong k-coloring of a hypergraph assigns distinct colors to every member of a hyperedge and uses $$k$$ colors. When the hypergraph is $$k$$-uniform, this problem is equivalent to the problem you describe. Further, this problem is NPC as shown by Colbourn, Jungnickel and Rosa [1].