Palette sparsification beyond (∆ + 1) vertex coloring

Noga Alon, Sepehr Assadi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020
EditorsJaroslaw Byrka, Raghu Meka
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771641
DOIs
StatePublished - Aug 1 2020
Event23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 - Virtual, Online, United States
Duration: Aug 17 2020Aug 19 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume176
ISSN (Print)1868-8969

Conference

Conference23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020
CountryUnited States
CityVirtual, Online
Period8/17/208/19/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Graph coloring
  • List-coloring
  • Palette sparsification
  • Sublinear algorithms

Fingerprint Dive into the research topics of 'Palette sparsification beyond (∆ + 1) vertex coloring'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Assadi, S. (2020). Palette sparsification beyond (∆ + 1) vertex coloring. In J. Byrka, & R. Meka (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020 [APPROX6] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 176). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.6