Is vertex coloring of hypergraph with no uniformity restriction NP-hard?

Question

Is vertex coloring of a hypergraph with no uniformity restriction NP-hard? I have seen papers that show vertex coloring for a k-unoform hypergraph is NP-hard. However I could not find any source that explicitly says whether or not a vertex coloring in the general case (not just k-uniform) hypergraph is NP-hard.

Answer 1

Before answering this question, there are many things have to be explained such as coloring and uniformity in hypergraphs. I will use here different notations.

A k-coloring of a hypergraph H = (V, E) is a function assigning colors from {1, 2, . . . , k} to vertices of H in such a way that no edge is monochromatic (no edge has all vertices of the same color - besides singletons).

The chromatic number of a hypergraph H, is the smallest integer k for which H admits a k-coloring.

A hypergraph H=(V,E) is called r-uniform, If all edges have cardinality (size) exactly r. The cardinality of an hyperedge (e) is the number of vertices in (e).

You have already found that a k-coloring for r-uniform hypergraph, r>=3, is NP-hard. If this is true (which is true) then it is NP-hard for general hypergraphs, because this is the smaller problem than general hypergraphs.

To convince you that this is true, let's have a look to the Berg definition of r-uniform hypergraph 1. This is equivalent to the above definition.

Let's denote r(H)=Max|E_i|, and s(H)=min|E_i|. H is r-uniform hypergraph if r(H)=s(H). Now if I can color this in polynomail time, which means I found the smallest integer k for which H admits a k-coloring. Then for general hypergraphs when s(H) could be smaller than r(H), we will be able to color the vertices in polynomial time.

To find the exact value of the chromatic number of a hypergraph is NP-hard.