Correspondence coloring with a fixed forbidden subgraph

What OpenAI claims

Proves the Alon–Krivelevich–Sudakov coloring conjecture in correspondence-coloring form: graphs avoiding any fixed subgraph F need O_F(Δ/log Δ) colors when their maximum degree Δ is sufficiently large. Also proves the Ajtai–Erdős–Komlós–Szemerédi independence conjecture: for fixed r ≥ 4, every n-vertex Kr-free graph of average degree d ≥ 2 has an independent set of size Ω_r(n log d/d). (Lean)

Papers (2)

1. Correspondence coloring graphs with a forbidden clique

   5 October 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract For every fixed integer r ≥ 4, we prove that every Kr-free graph of sufficiently large maximum degree Δ has correspondence chromatic number O_r(Δ/log Δ). This resolves the Alon–Krivelevich–Sudakov coloring conjecture in the stronger correspondence-coloring form. The same bound, with a constant depending on F, holds when any fixed graph F is excluded as an ordinary subgraph. Ordinary and list coloring satisfy the same bounds.

2. A logarithmic independence bound for clique-free graphs

   25 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract For every fixed integer r ≥ 4, every Kr-free graph on n vertices with average degree d ≥ 2 has an independent set of size at least c_r n log d/d, where c_r > 0 depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.

Status

Preprint. The papers have 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.