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 Kr-free graph of average degree d ≥ 2 has an independent set of size $\Omega_r(n\log d/d)$.
released 2026-10-05 | 1 theorem · 8 lemmas · 13 proofs · 12,408 words |
PLAY LEVEL 1 »(pdf)
For every fixed integer r ≥ 4, we prove that every Kr-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.
released 2026-09-25 | 2 theorems · 9 lemmas · 13 proofs · 7,507 words |
PLAY LEVEL 2 »(pdf)
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\gt 0$ depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.