{"id":"openai-math/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs","pdf":"https://github.com/openai/math/blob/main/preprints/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026","tags":["computational-complexity","graph-coloring","independent-sets","np-hardness"],"score":0,"title":"Hardness of finding large independent sets in three-colorable graphs","domain":"Theoretical computer science","family":"106","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove that, for every fixed $`0\\lt \\delta\\lt 1/3`$, it is NP-hard to distinguish three-colorable graphs from graphs in which every independent set has fewer than δ times the number of vertices. Consequently, for every fixed integer c ≥ 3, finding a proper c -coloring of a three-colorable graph is NP-hard.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":true,"family_title":"Hardness of coloring three-colorable graphs"}