Coloring graphs with forbidden bipartite subgraphs
share
A conjecture of Alon, Krivelevich, and Sudakov states that, for any graph F, there is a constant c_F > 0 such that if G is an F-free graph of maximum degree Δ, then χ(G) ≤ c_F Δ / 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 K_t,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.
READ FULL TEXT