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\mathrm{/}17+\text{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\mathrm{/}24+\text{eps})$-satisfying assignment.