Browse › Combinatorics › 184 Correspondence coloring with a fixed forbidden subgraph
Correspondence coloring graphs with a forbidden clique
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
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.
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.
Follow-up works
- Kaizhe Chen, A note on the logarithmic exponent of Ramsey number r(4,t) (arXiv:2610.15293, 11 October 2026). Cites this paper as proving the Alon–Krivelevich–Sudakov coloring conjecture, and says the coloring theorem lets the author avoid the log log t loss from Shearer's bound in deriving r(4,t) = t³/(log t)^(2+o(1)).
Possibly relevant literature (found by the agent, not checked)
- J. Anderson, A. Dhawan, A. Kuchukova, Coloring locally sparse graphs (arXiv:2402.19271, 2024, revised 2025). Proves list and correspondence coloring bounds for locally sparse graphs in the color-degree setting, which may bear on the paper's discussion of the Alon–Krivelevich–Sudakov and Vu local-sparsity bounds (Section 1.1).
- A. Dhawan, Bounds for the independence and chromatic numbers of locally sparse graphs (arXiv:2403.03054, 2024; Annals of Combinatorics 2026). Gives correspondence-coloring bounds for graphs with few r-cliques in each neighbourhood that retain a log log Δ/log Δ term, bearing on the paper's statement that earlier clique-exclusion bounds keep the log log Δ factor.
Digests and expositions
- Latent Seminar, Forbidden subgraphs, independence, and correspondence coloring (2026-10-07). Explains both manuscripts' weighted triangle estimates and vertex splitting, including the additional participation bound needed for correspondence coloring, while explicitly disclaiming independent verification of the complete proofs. [family-level]
- AI Proved What?, Forbid a clique, gain a log? (Episode 184, October 2026). Provides an animated exposition and transcript covering both claimed bounds, examples distinguishing list and correspondence coloring, and the stated formalization scope. [AI-generated per source] [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 184
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026,
author = {{OpenAI}},
title = {{Correspondence coloring graphs with a forbidden clique}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf}{OAI:Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/184.md. The Lean statements have not been checked by people against the paper's claims.
Family 184: 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)$.
Other papers in this family:
- A logarithmic independence bound for clique-free graphs · September 25, 2026