Correspondence coloring with a fixed forbidden subgraph

Proves the Alon–Krivelevich–Sudakov coloring conjecture in correspondence-coloring form: graphs avoiding any fixed subgraph F need O_F(\Delta/\log\Delta) 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 K_r-free graph of average degree d ≥ 2 has an independent set of size \Omega_r(n\log d/d). (Lean)

Manuscripts (2)

Correspondence coloring graphs with a forbidden clique

October 5, 2026 · source · cite as \cite{OAI:Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026}

For every fixed integer r ≥ 4, we prove that every K_r-free graph of sufficiently large maximum degree Δ has correspondence chromatic number O_r(\Delta/\log\Delta). 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.

A logarithmic independence bound for clique-free graphs

September 25, 2026 · source · Lean formalization available · cite as \cite{OAI:A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026}

For every fixed integer r ≥ 4, every K_r-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\gt 0 depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.

Result 184 · Combinatorics. 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.