## Palette Sparsification Beyond (∆ + 1) Vertex Coloring

Authors:
Noga Alon, Sepehr Assadi

Conference:
RANDOM 2020

Abstract:
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,

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}.

Conference version:
[PDF]

Full version:
[arXiv]

Blog post:
[Property Testing Review]