2025/11/21 by Abhishek Dhawan, Oliver Janzer, Dhawan, Abhishek +3 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2511.17191
Alon, Krivelevich, and Sudakov conjectured in 1999 that every F-free graph of maximum degree at most Δ has chromatic number O(Δ/ log Δ). This was previously known only for almost bipartite graphs, that is, for subgraphs of K1,t,t (verified by Alon, Krivelevich, and Sudakov themselves), while most recent results were concerned with improving the leading constant factor in the case where F is almost bipartite. We prove this conjecture for all 3-colorable graphs F, i.e. subgraphs of Kt,t,t, representing the first progress toward the conjecture since it was posed. A closely related conjecture of Ajtai, Erdős, Komlós, and Szemerédi from 1981 asserts that for every graph F, every n-vertex F-free graph of average degree d contains an independent set of size Ω(n log d / d). We prove this conjecture in a strong form for all 3-colorable graphs F. More precisely, we show that every n-vertex Kt,t,t-free graph of average degree d contains an independent set of size at least (1 - o(1)) n log d / d, matching Shearer's celebrated bound for triangle-free graphs (the case t = 1) and thereby yielding a substantial strengthening of it. Our proof combines a new variant of the Rödl nibble method for constructing independent sets with a Turán-type result on Kt,t,t-free graphs.