Coloring locally sparse graphs

James Anderson, Abhishek Dhawan, Aiya Kuchukova

A graph $G$ is $k$-locally sparse if for each vertex $v\in V(G)$, the subgraph induced by its neighborhood contains at most $k$ edges. Alon, Krivelevich, and Sudakov showed that f…