# Hypergraph Coloring Complexity

Dear can you help I am confused about the complexity of hypergraph coloring and finding the minimum number of colors

Finding the minimum number of colors for strongly coloring a k-uniform hypergraph is NP-Hard or NP-Complete ?

Strongly coloring a k-uniform hypergraph is NP-hard or NP-complete ?

Can you provide a reference and which algorithm is best for strongly coloring a k-uniform hypergraph?

• Could you add the definition of a strong coloring? – Gamow Apr 8 '18 at 12:34
• Calculating the minimum number of colors (chromatic number) required to strongly coloring a k-uniform hypergraph is NP-Hard or NP-Complete ? I mean by strongly coloring that the vertices in the same hyperedge assigned different colors. Note : I am not asking about if given an m number of colors a hypergraph is strongly colorable or not ? I want to calculate the minimum number of colors required to strongly coloring a k-uniform hypergraph The problem of Strongly coloring a k-uniform hypergraph is NP-hard or NP-complete ? – Salwa Mostafa Apr 9 '18 at 13:18
• Now this sounds like homework. You should start by taking a closer look at the case k=2. – Gamow Apr 9 '18 at 17:10
• cross-posted and solved here: cs.stackexchange.com/questions/93299/… – domotorp Jul 20 '18 at 22:17