2026-07-22T12:29:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12609 2024-03-06T10:51:14Z ddc:004 open_access

Palette Sparsification Beyond (Δ+1) Vertex Coloring Alon, Noga Assadi, Sepehr Graph coloring palette sparsification sublinear algorithms list-coloring 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noga Alon and Sepehr Assadi 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.6 urn:nbn:de:0030-drops-126096 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.6 eng https://creativecommons.org/licenses/by/3.0/legalcode