Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 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 \ge t$. We show that for all $t \ge 3$, it is NP-hard to find a $c$-coloring when $c \le 2t-2$. In the regime where $t$ is small, this improves, via a unified approach, the previously best known NP-hardness result of $c \le \max\{2t-5, t + 2\lfloor t/3\rfloor - 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 \ge 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 = \lceil 3k/2\rceil$, 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.