Family 184CombinatoricsLeanNot yet digested
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 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-free graph of average degree d ≥ 2 has an independent set of size .
Manuscripts in this family · 2
Correspondence coloring graphs with a forbidden clique
Oct 5, 2026·correspondence-coloring-forbidden-clique.pdf
For every fixed integer r ≥ 4, we prove that every K-free graph of sufficiently large maximum degree Δ has correspondence chromatic number . 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
Sep 25, 2026·paper.pdfLean
For every fixed integer r ≥ 4, every K-free graph on n vertices with average degree d ≥ 2 has an independent set of size at least , where depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.