TY - JOUR
T1 - Linial for lists.
AU - Maus, Yannic
AU - Tonoyan, Tigran
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2022/12
Y1 - 2022/12
N2 - 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).
AB - 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).
KW - Color reduction
KW - Cover-free family
KW - Deterministic distributed coloring
KW - List coloring
UR - http://www.scopus.com/inward/record.url?scp=85130489263&partnerID=8YFLogxK
U2 - 10.1007/s00446-022-00424-y
DO - 10.1007/s00446-022-00424-y
M3 - Article
SN - 0178-2770
VL - 35
SP - 533
EP - 546
JO - Distributed Computing
JF - Distributed Computing
IS - 6
ER -