New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
classification
💻 cs.CC
keywords
coloringcoverfindgivenlabelnp-hardto-1assignment
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.