Palette sparsification beyond (∆ + 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 ∆, sampling O(log n) colors per each vertex independently from ∆ + 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 (∆ + 1) coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we focus on palette sparsification beyond (∆ + 1) coloring, in both regimes when the number of available colors is much larger than (∆ + 1), and when it is much smaller. In particular, We prove that for (1 + ε)∆ coloring, sampling only Oε(√log n) colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors - this shows a separation between (1 + ε)∆ and (∆ + 1) coloring in the context of palette sparsification. A natural family of graphs with chromatic number much smaller than (∆ + 1) are triangle-free graphs which are O(_ln∆/_∆ ) colorable. We prove a palette sparsification theorem tailored to these graphs: Sampling O(∆^γ + √log n) colors per vertex is sufficient and necessary to obtain a proper Oγ (_ln∆/_∆ ) coloring of triangle-free graphs. We also consider the “local version” of graph coloring where every vertex v can only be colored from a list of colors with size proportional to the degree deg(v) of v. We show that sampling Oε(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 + ε) · deg(v) arbitrary colors, or even only deg(v) + 1 colors when the lists are the sets {1,..., deg(v) + 1}. 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.