Alon–Krivelevich–Sudakov conjecture on coloring graphs with forbidden subgraphs

About 5 years old · traced to 2021

Let $F$ be a graph. A graph $G$ is $F$ -free if it contains no copy of $F$ ; write $\chi(G)$ for its chromatic number and let $\Delta$ be its maximum degree.

Alon–Krivelevich–Sudakov conjecture. For every graph $F$ , there is a constant $c_F>0$ such that, whenever $G$ is an $F$ -free graph of maximum degree $\Delta\geqslant 2$ , one has

\chi(G)\leqslant c_FDelta/\log \Delta.

Alon, Krivelevich, and Sudakov verified the conjecture for a class of graphs including all bipartite graphs, and subsequent work gives sharper bounds for some complete bipartite forbidden graphs. The conjecture is therefore resolved for some $F$ , but the general assertion remains open.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Alon–Krivelevich–Sudakov conjecture on coloring graphs with forbidden subgraphs
Let $F$ be a graph, and let $G$ be an $F$ -free graph of maximum degree $\Delta$ . Here, $F$ -free means that $G$ has no subgraph, not necessarily induced, isomorphic to $F$ .

Alon–Krivelevich–Sudakov conjecture. If $G$ is an $F$ -free graph of maximum degree $\Delta$ , then
$\chi(G)=O\left(\frac{\Delta}{\log\Delta}\right),$
where the implied constant may depend on $F$ .

This conjecture asks whether the extra $\log\log\Delta$ factor in the best general upper bound for the chromatic number of graphs with bounded maximum degree can be removed. It has been verified for almost bipartite forbidden graphs, but the general conjecture remains open.
source: James Anderson, Anton Bernshteyn and Abhishek Dhawan, “Coloring graphs with forbidden almost bipartite subgraphs”, arXiv:2203.07222 (2025).

References

Primary source

James Anderson, Anton Bernshteyn and Abhishek Dhawan, “Coloring graphs with forbidden bipartite subgraphs”, arXiv:2107.05595 (2022).

Posted 1 month ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

RemarkAI-assistedClaimed by OpenAI. For every fixed finite forbidden subgraph F, claims a correspondence-chromatic bound C_F Delta/log Delta for finite simple F-free base graphs G of sufficiently large maximum degree Delta. This implies the ordinary Alon-Krivelevich-Sudakov bound chi(G)<=c_F Delta/log Delta for every Delta>=2 after enlarging c_F using the greedy bound for the finitely many smaller degrees. F-freeness and degree apply to G; no analogous condition on a DP-cover graph is asserted.See full solutionHide full solution

Claimed by OpenAI.

For every fixed finite forbidden subgraph F, claims a correspondence-chromatic bound C_F Delta/log Delta for finite simple F-free base graphs G of sufficiently large maximum degree Delta. This implies the ordinary Alon-Krivelevich-Sudakov bound chi(G)<=c_F Delta/log Delta for every Delta>=2 after enlarging c_F using the greedy bound for the finitely many smaller degrees. F-freeness and degree apply to G; no analogous condition on a DP-cover graph is asserted.

Theorem1.1 gives the correspondence-chromatic bound for K_r-free base graphs for each fixed r>=4. Corollary1.2 takes r=max(4,|V(F)|), because every F-free graph is K_r-free. Ordinary chromatic number is at most correspondence chromatic number. For 2<=Delta<Delta_F, chi(G)<=Delta+1 extends the ordinary bound after increasing the F-dependent constant. The forbidden graph is a subgraph, not necessarily induced.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf

OpenAI-184-01-Correspondence-coloring-graphs-with-a-forbidden-clique.pdf484,084 bytesOpen