Locally-Iterative Distributed (Δ+ 1)
Leonid Barenboim, Michael Elkin, Uri Goldenberg · 2018
We consider graph coloring and related problems in the distributed message-passing model. \em Locally-iterative algorithms are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its 1 - hop-neighborhood. In STOC'93 Szegedy and Vishwanathan showed that any locally-iterative (Δ + 1)-coloring algorithm requires Ω(Δ log Δ + log^* n) rounds, unless there exists "a very special type of coloring that can be very efficiently reduced" \citeSV93.