论文标题
重新审视当地冲突着色：列表的母线
Local Conflict Coloring Revisited: Linial for Lists
论文作者
论文摘要
Linial的著名颜色还原算法将具有最高度$δ$的图的给定$ m $颜色减少到$ O（δ^2 \ log m）$ - 颜色，在本地模型中的单轮中。当节点被限制从允许的颜色列表中选择其颜色时，我们显示出类似的结果：如果每个节点都有$ $ω的列表（β^2（\ logβ + log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log | \ nog | | \ n o \ co），则给定最大超级$β$的$ m $彩色颜色c}他们可以在本地型号的两轮中选择两轮颜色。此外，节点的通信本质上包括将其列表发送给邻居。这是作为一个框架的一部分获得的，该框架还包含一系列的颜色降低（带有替代证明）作为特殊情况。我们的结果还导致列表着色算法有缺陷。作为推论，我们改善了最先进的本地$（deg+1）$ - 列表着色算法，来自Barenboim等人。 [PODC'18]通过将运行时稍微降低到$ O（\ sqrt {δ\logΔ}））+\ log^* n $，并大大降低了消息大小（从巨大到大约$δ$）。我们的技术灵感来自Fraigniaud等人的当地冲突着色框架。 [焦点16]。
Linial's famous color reduction algorithm reduces a given $m$-coloring of a graph with maximum degree $Δ$ to a $O(Δ^2\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 $Ω(β^2 (\log β+\log\log m + \log \log |\mathcal{C}|))$ from a color space $\mathcal{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'18] by slightly reducing the runtime to $O(\sqrt{Δ\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].
