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\in V(G)$, the subgraph induced by its neighborhood contains at most $k$ cliques of size $r$. For $r\ge 3$ and $\epsilon \in [0,1]$, we show that an $n$-vertex $({\mathrm{\Delta }}^{\epsilon r},r)$-locally-sparse graph $G$ of maximum degree $\mathrm{\Delta }$ satisfies $\alpha (G)\ge (1-o(1)){\displaystyle \frac{n}{\eta \mathrm{\Delta }}}$ and $\chi (G)\le \mathrm{\Theta }\left(\eta \mathrm{\Delta }\right)$, where $\eta :=\epsilon +{\displaystyle \frac{r\log \log \mathrm{\Delta }}{\log \mathrm{\Delta }}}$. For $\epsilon$ not too large, the hidden constant in the $\mathrm{\Theta }(\cdot )$ can be taken to be $1+o(1)$. Setting $\epsilon =0$, we recover classical results on $K_{r+1}$-free graphs due to Shearer and Johansson, which were more recently improved by Davies, Kang, Pirot, and Sereni. We prove a stronger result on the independence number in terms of the occupancy fraction in the hard-core model, and establish a local version of the coloring result in the more general setting of correspondence coloring.