New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover
Per Austrin, Ryan W. O’Donnell, Li-Yang Tan, John C. Wright · ACM Transactions on Computation Theory · 2014
We show that given a 3-colorable graph, it is NP-hard to find a 3-coloring with (16/17 + ε) of the edges bichromatic. In a related result, we show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a (23/24 + ε)-satisfying assignment.