Browse › Theoretical computer science › 106 Hardness of coloring three-colorable graphs
Hardness of finding large independent sets in three-colorable graphs
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI, Hardness of coloring three-colorable graphs: Lean scope note (OpenAI Math Release, lean/docs/106.md, 2026). The scope note describes a formalized deterministic polynomial-time reduction from binary 3SAT with three-colorable completeness and independent-set density below each fixed 0 < δ < 1/3 in the unsatisfiable case, including the full adjacency-matrix output in the runtime bound, and points to a comparator file
IndependentSets.lean.
Related prior literature mentioned by others
- Yumou Fei, Dor Minzer, Shuo Wang, On the Hardness of 4-to-1 Games with Perfect Completeness (arXiv:2610.12378, 8 October 2026; also ECCC TR26-179, 14 September 2026, revised 8 October 2026). Independent human proof of the 4-to-1 Games Conjecture; its Corollary 1.7 gives the 3-colorable vs. not k-colorable gap, and Corollary 1.9 gives small independent-set density with an 8-colorable completeness promise. The paper cites the ECCC version, and secondary coverage of family 106 mentions it alongside this result.
Possibly relevant literature (found by the agent, not checked)
- Marcin Wrochna, Stanislav Živný, Improved hardness for H-colourings of G-colourable graphs (arXiv:1907.00872, SODA 2020). Proves NP-hardness of coloring k-colorable graphs with C(k,⌊k/2⌋)−1 colors for k ≥ 4, which is prior work on Corollary 1.2 (all fixed 3 ≤ k ≤ c) beyond the k = 3 results the introduction surveys.
- Sangxia Huang, Improved Hardness of Approximating Chromatic Number (arXiv:1301.5216, 2013). Proves NP-hardness of coloring K-colorable graphs with fewer than 2^{K^{1/3}} colors for large K, more prior unconditional work on the general-k case of Corollary 1.2.
- David Karger, Rajeev Motwani, Madhu Sudan, Approximate Graph Coloring by Semidefinite Programming (arXiv:cs/9812008, JACM 1998). The original SDP coloring algorithm for 3-colorable graphs, from which the 2024–2026 algorithms cited in the paper's "algorithmic work" paragraph descend.
Digests and expositions
- Open Mathematics Courses / Claude Opus 5.5, Large independent sets in three-colorable graphs (Open Mathematics Courses, undated). Six lessons with exercises explain this paper's phase-space construction, Lipschitz-function and answer-list arguments, alignment theorem, and coefficient test, explicitly retaining PCP and parallel repetition as external inputs and stating that independent review is incomplete. [AI-generated per source]
News and blogs
- postcutoff.com, OpenAI model claims a proof of Khot's Unique Games Conjecture, with Lean formalization (filed 7 October 2026). A release overview that lists result 106 as "NP-hardness of colouring 3-colourable graphs with any constant number of colours" and points to the Fei–Minzer–Wang ECCC report as stating a related consequence. [AI-generated per source]
Elsewhere
- Emergent Mind: family 106
Independent sites; their content is not reviewed here.
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}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/106.md. The Lean statements have not been checked by people against the paper's claims.
Family 106: Hardness of coloring three-colorable graphs
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.
This is the only paper in this family.