2021/07/12 by James Anderson, Anderson, James, Anton Bernshteyn +3 · 4 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Combinatorics (math.CO) #Complete bipartite graph #Computer science #Conjecture #Constant (computer programming) #Delta #Discrete Mathematics (cs.DM) #Discrete mathematics #Edge coloring #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph coloring #Graph power #Limits and Structures in Graph Theory #Line graph #Mathematics #Physics #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.2107.05595
published in arXiv (Cornell University) (Cornell University) · 22 pp
openalex publication_date 2021/07/12 · arxiv created 2022/01/21 · arxiv updated 2022/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
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.