1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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