The Alon-Krivelevich-Sudakov conjecture: graphs with a fixed forbidden subgraph have chromatic number O(Delta/log Delta)

Theorem 1.1: for every $r\ge4$ there are $C_r$ and $\Delta_r$ such that every $K_r$-free graph of maximum degree $\Delta\ge\Delta_r$ has correspondence (DP) chromatic number at most $\lceil C_r\Delta/\log\Delta\rceil$; Corollary 1.2 gives the same for any fixed forbidden subgraph $F$, which implies the conjecture for ordinary and list coloring. The proof is a round-based random partial coloring with weighted lists, controlled by an entropy potential and local adjustments that offset triangle correlations. Constants and thresholds are not optimized; no explicit leading constant is claimed.

Theorem 1.1: for every $r\ge4$ there are $C_r$ and $\Delta_r$ such that every $K_r$-free graph of maximum degree $\Delta\ge\Delta_r$ has correspondence (DP) chromatic number at most $\lceil C_r\Delta/\log\Delta\rceil$; Corollary 1.2 gives the same for any fixed forbidden subgraph $F$, which implies the conjecture for ordinary and list coloring. The proof is a round-based random partial coloring with weighted lists, controlled by an entropy potential and local adjustments that offset triangle correlations. Constants and thresholds are not optimized; no explicit leading constant is claimed.