Finding a proper coloring of a t -colorable graph G with t colors is a classic NP-hard problem when t 3 . In this work, we investigate the approximate coloring problem in which the objective is to find a proper c -coloring of G where c t . We show that for all t 3 , it is NP-hard to find a c -coloring when c 2 t − 2 . In the regime where t is small, this improves, via a unified approach, the previously best known NP-hardness result of c max 2 t − 5 t + 2 t 3 − 1 . For example, we show that 6 -coloring a 4 -colorable graph is NP-hard, improving on the NP-hardness of 5 -coloring a 4 -colorable graph.

We also generalize this to related problems on the strong coloring of hypergraphs. A k -uniform hypergraph H is t -strong colorable (where t k ) if there is a t -coloring of the vertices such that no two vertices in each hyperedge of H have the same color. We show that if t = 3 k 2 , then it is NP-hard to find a 2 -coloring of the vertices of H such that no hyperedge is monochromatic. We conjecture that a similar hardness holds for t = k + 1 . We establish the NP-hardness of these problems by reducing from the hardness of the Label Cover problem, via a ``dictatorship test'' gadget graph. By combinatorially classifying all possible colorings of this graph, we can infer labels to provide to the label cover problem. This approach generalizes the ``weak polymorphism'' framework of (Austrin-Guruswami-Håstad, 2014), though interestingly our results are ``PCP-free'' in that they do not require any approximation gap in the starting Label Cover instance.