Coloring locally sparse graphs

A graph G is k-locally sparse if for each vertex v ∈ V(G), the subgraph induced by its neighborhood contains at most k edges. Alon, Krivelevich, and Sudakov showed that for $f > 0$ if a graph G of maximum degree Δ is Δ²/f-locally-sparse, then χ(G) = O(Δ/log f). We introduce a more general notion of local sparsity by defining graphs G to be $(k, F)$-locally-sparse for some graph F if for each vertex v ∈ V(G) the subgraph induced by the neighborhood of v contains at most k copies of F. Employing the R\"{o}dl nibble method, we prove the following generalization of the above result: for every bipartite graph F, if G is $(k, F)$-locally-sparse, then χ(G) = O( Δ /log(Δ k-1/|V(F)|)). This improves upon results of Davies, Kang, Pirot, and Sereni who consider the case when F is a path. Our results also recover the best known bound on χ(G) when G is K1, t, t-free for t ≥ 4, and hold for list and correspondence coloring in the more general so-called ''color-degree'' setting.