Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model

Shiri Chechik, Doron Mukhtar

In this paper, we consider distributed coloring for planar graphs with a small number of colors. We present an optimal (up to a constant factor) $O(\log n)$ time algorithm for 6-c…