New NP-hardness results for 3-Coloring and 2-to-1 Label Cover

Per Austrin, Ryan O'Donnell, Li-Yang Tan +1

We show that given a 3-colorable graph, it is NP-hard to find a 3-coloring with $(16/17 + \eps)$ of the edges bichromatic. In a related result, we show that given a satisfiable ins…