Bounds for the independence and chromatic numbers of locally sparse graphs

In this note we consider a more general version of local sparsity introduced recently by Anderson, Kuchukova, and the author. In particular, we say a graph G = (V, E) is (k, r) -locally-sparse if for each vertex v V (G), the subgraph induced by its neighborhood contains at most k cliques of size r. For r 3 and 0, 1, we show that a (^ r, r) -locally-sparse graph G of maximum degree satisfies (G) = (n) and (G) = O (), where: =\, \, r { \}. As Kₑ+₁-free graphs are (k, r) -locally-sparse for any k, we asymptotically recover classical results of Shearer and Johansson by setting = 0. We prove a stronger bound on the independence number in terms of the average degree, and establish a local version of the coloring result in the more general setting of correspondence coloring.