2026-07-24T06:08:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12469 2024-03-06T10:50:13Z ddc:004 open_access

d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors Guruswami, Venkatesan Sandeep, Sai graph coloring hardness of approximation The d-to-1 conjecture of Khot asserts that it is NP-hard to satisfy an ε 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 is 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 is known under a certain "fish-shaped" variant of the 2-to-1 conjecture. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan Guruswami and Sai Sandeep 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.62 urn:nbn:de:0030-drops-124694 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.62 eng https://creativecommons.org/licenses/by/3.0/legalcode