Palette Sparsification for Graphs with Sparse Neighborhoods
<|reference_start|>Palette Sparsification for Graphs with Sparse Neighborhoods: A celebrated palette sparsification result of Assadi, Chen, and Khanna states that in every $n$-vertex graph of maximum degree $\Delta$, sampling $\Theta(\log n)$ colors per vertex from $\{1,\ldots,\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(\Delta/\log \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 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(\Delta/\log (\Delta/\sqrt{k}))$-colorable. For any $\alpha\in(0,1)$ and $k\ll\Delta^{2\alpha}$, let $G$ be a $k$-locally-sparse graph. We show the following for $q=\Theta\left(\Delta/\log\left(\Delta^\alpha/\sqrt{k}\right)\right)$:   1. Sampling $O(\Delta^\alpha+\sqrt{\log n})$ colors per vertex is sufficient to obtain a proper $q$-coloring of $G$ from the sampled colors.   2. There exists a single-pass streaming algorithm which computes a proper $q$-coloring of $G$ with high probability using $\tilde O(n\Delta^{2\alpha})$ space.   3. There exists a randomized non-adaptive sublinear-time algorithm which computes a proper $q$-coloring of $G$ with high probability using at most $\tilde O\left(n^{\frac32+\frac{\alpha}{2-2\alpha}}\right)$ queries.   Our results recover and improve upon earlier work of Alon and Assadi. 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.<|reference_end|>
@article{dhawan2024palette,
    title={Palette Sparsification for Graphs with Sparse Neighborhoods},
    author={Abhishek Dhawan},
    journal={arXiv preprint arXiv:2408.08256},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.08256},
    primaryClass={cs.DS cs.DM math.CO}
}