  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-coloring planar graphs. Our algorithm is
based on a novel technique that in a nutshell detects small structures that can
be easily colored given a proper coloring of the rest of the vertices and
removes them from the graph until the graph contains a small enough number of
edges. We believe this technique might be of independent interest.
  In addition, we present a lower bound for 4-coloring planar graphs that
essentially shows that any algorithm (deterministic or randomized) for
$4$-coloring planar graphs requires $\Omega(n)$ rounds. We therefore completely
resolve the problems of 4-coloring and 6-coloring for planar graphs in the
LOCAL model.
