Linial for lists.

Yannic Maus, Tigran Tonoyan

Research output: Contribution to journalArticlepeer-review

Abstract

Linial’s famous color reduction algorithm reduces a given m-coloring of a graph with maximum degree Δ to an O(Δ 2log m) -coloring, in a single round in the LOCAL model. We give 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 Ω(β 2(log β+ log log m+ log log | C|)) from a color space C 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, pp 437–446, 2018) by slightly reducing the runtime to O(ΔlogΔ)+log∗n and significantly reducing the message size (from ΔO(log∗Δ) to roughly Δ). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. (in: FOCS, pp 625–634, 2016).

Original languageEnglish
Pages (from-to)533-546
Number of pages14
JournalDistributed Computing
Volume35
Issue number6
DOIs
Publication statusPublished - Dec 2022

Keywords

  • Color reduction
  • Cover-free family
  • Deterministic distributed coloring
  • List coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Linial for lists.'. Together they form a unique fingerprint.

Cite this