The d-to-1 conjecture of Khot asserts that it is NP-hard to satisfy an epsilon fraction of constraints of a satisfiable d-to-1 Label Cover instance, for arbitrarily small ε > 0. We prove that the d-to-1 conjecture for any fixed d implies the hardness of coloring a 3-colorable graph with C colors for arbitrarily large integers C.
Earlier, the hardness of O(1)-coloring a 4-colorable graphs was known under the 2-to-1 conjecture, which is the strongest in the family of d-to-1 conjectures, and the hardness for 3-colorable graphs was known under a certain “fish-shaped” variant of the 2-to-1 conjecture.
Joint work with Venkatesan Guruswami.