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 (/ 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\"odl 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 (/ (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 K₁, ₓ, ₓ-free for t 4, and hold for list and correspondence coloring in the more general so-called ''color-degree'' setting.