∑math20

Theoretical computer science · Result 106

Hardness of coloring three-colorable graphs

1 paperLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 1

First page of Hardness of finding large independent sets in three-colorable graphs

Hardness of finding large independent sets in three-colorable graphs

OpenAI · 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.

Read PDF Download Source

Cite
@misc{OAI:Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026,
  author = {{OpenAI}},
  title = {{Hardness of finding large independent sets in three-colorable graphs}},
  howpublished = {OpenAI Math Release preprint
                  \href{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}{OAI:Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

The formalized result shows hardness of finding large independent sets even under a three-colorability promise. For every fixed \(0<\delta<1/3\), a deterministic polynomial-time reduction maps binary 3SAT formulas to nonempty finite simple graphs. Satisfiable formulas produce three-colorable graphs; unsatisfiable formulas produce graphs whose largest independent set has fewer than \(\delta\) times the number of vertices. The complete adjacency-matrix output is included in the runtime bound.

Comparator links

ResultComparator statement
Independent-set hardness in three-colorable graphsIndependentSets.lean

Scope note on GitHub →