# Palette Sparsification Beyond (Delta+1) Vertex Coloring

arXiv: https://arxiv.org/abs/2006.10456 · HTML: https://mlsanity.com/paper/2006.10456/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2020.

## Built on by (most cited first, 1 of 1)

- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)

## Abstract (arXiv)

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.