Palette Sparsification for Graphs with Sparse Neighborhoods

A seminal palette sparsification result of Assadi, Chen, and Khanna states that in every $n$-vertex graph of maximum degree $\mathrm{\Delta }$, sampling $\mathrm{\Theta }(\log n)$ colors per vertex from $\{1,\dots ,\mathrm{\Delta }+1\}$ almost certainly allows for a proper coloring from the sampled colors. Alon and Assadi extended this work proving a similar result for $O(\mathrm{\Delta }\mathrm{/}\log \mathrm{\Delta })$-coloring triangle-free graphs. Apart from being interesting results from a combinatorial standpoint, their results have various applications to the design of graph coloring algorithms in different models of computation. In this work, we focus on locally sparse graphs, i.e., graphs with sparse neighborhoods. We say a graph $G=(V,E)$ is $k$-locally-sparse if for each vertex $v\in V$, the subgraph $G[N(v)]$ contains at most $k$ edges. A celebrated result of Alon, Krivelevich, and Sudakov shows that such graphs are $O(\mathrm{\Delta }\mathrm{/}\log (\mathrm{\Delta }\mathrm{/}\sqrt{k}))$-colorable. For any $\alpha \in (0,1)$ and $k\ll {\mathrm{\Delta }}^{2\alpha }$, let $G$ be a $k$-locally-sparse graph. For $q=\mathrm{\Theta }(\mathrm{\Delta }\mathrm{/}\log \left({\mathrm{\Delta }}^{\alpha }\mathrm{/}\sqrt{k}\right))$, we show that sampling $O({\mathrm{\Delta }}^{\alpha }+\sqrt{\log n})$ colors per vertex is sufficient to obtain a proper $q$-coloring of $G$ from the sampled colors. Setting $k=1$ recovers the aforementioned result of Alon and Assadi for triangle-free graphs. A key element in our proof is a proposition regarding correspondence coloring in the so-called color-degree setting, which improves upon recent work of Anderson, Kuchukova, and the author and is of independent interest.