License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.6
URN: urn:nbn:de:0030-drops-126096
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12609/
Alon, Noga ;
Assadi, Sepehr
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}.
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.
BibTeX - Entry
@InProceedings{alon_et_al:LIPIcs:2020:12609,
author = {Noga Alon and Sepehr Assadi},
title = {{Palette Sparsification Beyond (Δ+1) Vertex Coloring}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {6:1--6:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12609},
URN = {urn:nbn:de:0030-drops-126096},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.6},
annote = {Keywords: Graph coloring, palette sparsification, sublinear algorithms, list-coloring}
}
|
Keywords: |
|
Graph coloring, palette sparsification, sublinear algorithms, list-coloring |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.08.2020 |
