Correspondence coloring with a fixed forbidden subgraph
OpenAI research collection · 2 manuscripts · Source checked 2026-10-19
OpenAI's result summary
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(nlog d/d).
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Correspondence coloring graphs with a forbidden clique
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…
Full source abstract
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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
A logarithmic independence bound for clique-free graphs
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 nlog 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.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.