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.