2026-08-19T10:20:15Z https://drops.dagstuhl.de/oai

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

Local Conflict Coloring Revisited: Linial for Lists Maus, Yannic Tonoyan, Tigran distributed graph coloring list coloring low intersecting set families 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yannic Maus and Tigran Tonoyan 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.16 urn:nbn:de:0030-drops-130944 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode