Palette Sparsification Beyond (Delta+1) Vertex Coloring

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(logn) 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 Ovarepsilon(√logn) 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(fracDeltalnDelta) colorable. We prove that sampling O(Deltaγ + √logn) colors per vertex is sufficient and necessary to obtain a proper Oγ(fracDeltalnDelta) coloring of triangle-free graphs. * We show that sampling Ovarepsilon(logn) 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) · 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.