A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every $n$-vertex graph $G$ with maximum degree $\Delta$, sampling $O(\log{ n})$ colors per each vertex independently from $\Delta+1$ colors almost certainly allows for proper coloring of $G$ from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for $(\Delta+1)$ coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we further study palette sparsification problems: * We prove that for $(1+\varepsilon) \Delta$ coloring, sampling only $O_{ \varepsilon}(\sqrt{ \log{ n}})$ colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors. * A natural family of graphs with chromatic number much smaller than $(\Delta+1)$ are triangle-free graphs which are $O(\frac{ \Delta}{ \ln{ \Delta}})$ colorable. We prove that sampling $O(\Delta^{ \gamma} + \sqrt{ \log{ n}})$ colors per vertex is sufficient and necessary to obtain a proper $O_{ \gamma}(\frac{ \Delta}{ \ln{ \Delta}})$ coloring of triangle-free graphs. * We show that sampling $O_{ \varepsilon}(\log{ n})$ colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of $(1+\varepsilon) \cdot deg(v)$ arbitrary colors, or even only $deg(v)+1$ colors when the lists are the sets $\{ 1,\ldots,deg(v)+1\}$. Similar to previous work, our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.

Categories: cs.DS cs.DM

Palette Sparsification Beyond $(\Delta+1)$ Vertex Coloring