Hardness of coloring three-colorable graphs

What OpenAI claims

It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed 0 < δ < 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 δ n otherwise, where n is the number of vertices. (Lean)

Paper

1. Hardness of finding large independent sets in three-colorable graphs

   24 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract We prove that, for every fixed 0 < δ < 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.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.