Palette Sparsification Beyond (∆ + 1) Vertex Coloring
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,
- 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}.
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.
Conference version:
[PDF]