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

You can also prove yourself that this problem is NPC by a straightforward reduction from chromatic number. Essentially, you can add enough vertices around every edge and make them into cliques and you can make the reduction work.



[1] Colbourn, Charles J., Dieter Jungnickel, and Alexander Rosa. "The strong chromatic number of partial triple systems." Discrete applied mathematics 20.1 (1988): 31-38.