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.DISC.2020.16
URN: urn:nbn:de:0030-drops-130944
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13094/
Go to the corresponding LIPIcs Volume Portal

Maus, Yannic ; Tonoyan, Tigran

Local Conflict Coloring Revisited: Linial for Lists

pdf-format:
LIPIcs-DISC-2020-16.pdf (0.6 MB)

Abstract

Linial’s famous color reduction algorithm reduces a given m-coloring of a graph with maximum degree Δ to a O(Δ²log m)-coloring, in a single round in the LOCAL model. We show a similar result when nodes are restricted to choose their color from a list of allowed colors: given an m-coloring in a directed graph of maximum outdegree β, if every node has a list of size Ω(β² (log β+log log m + log log |?|)) from a color space ? then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial’s color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local (deg+1)-list coloring algorithm from Barenboim et al. [PODC'18] by slightly reducing the runtime to O(√{ΔlogΔ})+log^* n and significantly reducing the message size (from huge to roughly Δ). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS'16].

BibTeX - Entry

@InProceedings{maus_et_al:LIPIcs:2020:13094,
  author =	{Yannic Maus and Tigran Tonoyan},
  title =	{{Local Conflict Coloring Revisited: Linial for Lists}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13094},
  URN =		{urn:nbn:de:0030-drops-130944},
  doi =		{10.4230/LIPIcs.DISC.2020.16},
  annote =	{Keywords: distributed graph coloring, list coloring, low intersecting set families}
}

Keywords: distributed graph coloring, list coloring, low intersecting set families
Collection: 34th International Symposium on Distributed Computing (DISC 2020)
Issue Date: 2020
Date of publication: 07.10.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI