2021/07/12 by James Anderson, Anderson, James, Anton Bernshteyn +3 · 4 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2107.05595
openalex publication_date 2021/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A conjecture of Alon, Krivelevich, and Sudakov states that, for any graph F, there is a constant cF > 0 such that if G is an F-free graph of maximum degree Δ, then χ(G) ≤ cF Δ/ logΔ. Alon, Krivelevich, and Sudakov verified this conjecture for a class of graphs F that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot, and Sereni that if G is Kt,t-free, then χ(G) ≤ (t + o(1)) Δ/ logΔ as Δ→ ∞. We improve this bound to (1+o(1)) Δ/log Δ, making the constant factor independent of t. We further extend our result to the DP-coloring setting (also known as correspondence coloring), introduced by Dvořák and Postle.