It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed 0\lt \delta\lt 1/3, a deterministic polynomial-time reduction from 3SAT produces simple unweighted graphs that are three-colorable in the satisfiable case and have no independent set of size \delta n otherwise, where n is the number of vertices. (Lean)
Manuscript
Hardness of finding large independent sets in three-colorable graphs
September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026}
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.
Result 106 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md