文章基本信息
- 标题：Local Conflict Coloring Revisited: Linial for Lists
- 本地全文：下载
- 作者：Yannic Maus ; Tigran Tonoyan
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：179
- 页码：1-18
- DOI：10.4230/LIPIcs.DISC.2020.16
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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 ð'Z )) from a color space ð'Z 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(â^S{Î"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].
- 关键词：distributed graph coloring; list coloring; low intersecting set families
