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 γ :=max\ε,\,rloglog Δ/log Δ\. 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.