New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
  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 instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment. 
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
cs.CC