Linials famous color reduction algorithm reduces a given $m$-coloring of a graph with maximum degree $Delta$ to a $O(Delta^2log 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 $beta$, if every node has a list of size $Omega(beta^2 (log beta+loglog 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 Linials 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. [PODC18] by slightly reducing the runtime to $O(sqrt{DeltalogDelta})+log^* n$ and significantly reducing the message size (from huge to roughly $Delta$). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS16].
تحميل البحث