Under the auspices of the Computational Complexity Foundation (CCF) REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR19-116 | 5th May 2020 02:49

#### $d$-to-$1$ Hardness of Coloring $3$-colorable Graphs with $O(1)$ colors Revision #1
Authors: Venkatesan Guruswami, Sai Sandeep
Accepted on: 5th May 2020 02:49
Keywords:

Abstract:

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 $\epsilon > 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.

Changes to previous version:

The hardness is extended to $3$-colorable graphs by applying a subsequently discovered repeated arc digraph construction to reduce the chromatic number to 3. This version is the ICALP 2020 camera ready paper.

### Paper:

TR19-116 | 9th September 2019 23:28

#### $d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors

TR19-116
Authors: Venkatesan Guruswami, Sai Sandeep
Publication: 9th September 2019 23:29
The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ colors for arbitrarily large integers $C$. Earlier, this implication was only known under the $2$-to-$1$ conjecture, which is the strongest in the family of $d$-to-$1$ conjectures.
{"ft_lang_label":"__label__en","ft_lang_prob":0.90283257,"math_prob":0.9909682,"size":1430,"snap":"2022-40-2023-06","text_gpt3_token_len":385,"char_repetition_ratio":0.16409537,"word_repetition_ratio":0.50476193,"special_character_ratio":0.26223776,"punctuation_ratio":0.058139537,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.998144,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-09-30T09:24:34Z\",\"WARC-Record-ID\":\"<urn:uuid:12007de5-3e2e-495b-b93f-a60c910c90b1>\",\"Content-Length\":\"22867\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:78af975c-969a-4bd4-a488-6fba2745dfd0>\",\"WARC-Concurrent-To\":\"<urn:uuid:5f7e8ff8-9c56-4b7c-82ca-ddf9870e72f6>\",\"WARC-IP-Address\":\"132.77.150.87\",\"WARC-Target-URI\":\"https://eccc.weizmann.ac.il/report/2019/116/\",\"WARC-Payload-Digest\":\"sha1:66AWANAW47MGCFHNOHCVHS5VIZCPSNUY\",\"WARC-Block-Digest\":\"sha1:ZEA7ELAEQLCS2OH6RRMCD3YU7U3AIR4R\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030335448.34_warc_CC-MAIN-20220930082656-20220930112656-00034.warc.gz\"}"}