Strong inapproximability results on balanced rainbow-colorable hypergraphs (Q1715058)

The problem of coloring a hypergraph with few colors is a fundamental optimization problem. A $K$-uniform hypergraph $H=(V,E)$ is said to be $k$-colorable if there exists a coloring $c:V\to \{1, \dots, k\}$ of its vertices with $k$ colors so that no hyperedge is monochromatic. The problem of determining if a $K$-uniform hypergraph is $2$- colorable is a classic NP-hard problem when $K \geq 3$. Here, the authors are interested in the question of determining whether coloring a hypergraph remains hard even if we are promised that the hypergraph admits a coloring with natural stronger properties. A coloring of a hypergraph is called rainbow if every hyperedge contains at least one vertex from each color. The coloring is called perfectly balanced when each color appears the same number of times. The main result is to prove a strong hardness result that rules out coloring a hypergraph with $O(1)$ colors even when we are given that the hypergraph has a rainbow $k$-coloring with good balance between the colors (for any $k \geq 3$).