Coloring locally sparse graphs

Abstract

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 for $f>0$ if a graph $G$ of maximum degree $\hat{I}”$ is $\hat{I}{”}^2/f$-locally-sparse, then $\ddot{I}‡(G)=O\left(\hat{I}”/\log f\right)$. 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\in V(G)$ the subgraph induced by the neighborhood of $v$ contains at most $k$ copies of $F$. Employing the Rödl nibble method, we prove the following generalization of the above result: for every bipartite graph $F$, if $G$ is $(k,F)$-locally-sparse, then $\ddot{I}‡(G)=O\left(\hat{I}”/\log \left(\hat{I}”k^{-1/|V(F)|}\right)\right)$. 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 $\ddot{I}‡(G)$ when $G$ is $K_{1,t,t}$-free for $t\ge 4$, and hold for list and correspondence coloring in the more general so-called ''color-degree'' setting.

29 pages, 1 figure