## 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 language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020 |

Editors | Jaroslaw Byrka, Raghu Meka |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771641 |

DOIs | |

State | Published - Aug 1 2020 |

Event | 23rd 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 2020 → Aug 19 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 176 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 |
---|---|

Country/Territory | United States |

City | Virtual, Online |

Period | 8/17/20 → 8/19/20 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

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