Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models

Leonid Barenboim, Michael Elkin, Uri Goldenberg

We consider graph coloring and related problems in the distributed message-passing model. {Locally-iterative algorithms} are especially important in this setting. These are algorit…