摘要：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_ε(â^S{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(Î"^γ + â^S{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.
