New NP-hardness results for 3-Coloring and 2-to-1 Label Cover

2012/10/20 by Per Austrin, Ryan O’Donnell, Austrin, Per +5 · 2 citations
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1210.5648

openalex publication_date 2012/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Reinforced Generation of Combinatorial Structures: Hardness of Approximation
• Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration

Related

• A new point of NP-hardness for 2-to-1 Label Cover
• Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction
• 2^(log N)^1/10-o(1) Hardness for Hypergraph Coloring
• P=NP
• Improved Hardness of Approximating Chromatic Number