0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Could you add the definition of a strong coloring? $\endgroup$ – Gamow Apr 8 '18 at 12:34
  • $\begingroup$ 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 ? $\endgroup$ – Salwa Mostafa Apr 9 '18 at 13:18
  • $\begingroup$ Now this sounds like homework. You should start by taking a closer look at the case k=2. $\endgroup$ – Gamow Apr 9 '18 at 17:10
  • $\begingroup$ cross-posted and solved here: cs.stackexchange.com/questions/93299/… $\endgroup$ – domotorp Jul 20 '18 at 22:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.