New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
Austrin, Per · O'Donnell, Ryan · Tan, Li-Yang · Wright, John
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.