Distributed coloring in sparse graphs with fewer colors

Distributed coloring in sparse graphs with fewer colors
Abstract : We are concerned with efficiently coloring sparse graphs in
the distributed setting with as few colors as possible. According to
the celebrated Four Color Theorem, planar graphs can be colored with
at most 4 colors, and the proof gives a (sequential) quadratic
algorithm finding such a coloring. A natural problem is to improve
this complexity in the distributed setting. Using the fact that planar
graphs contain linearly many vertices of degree at most 6, Goldberg,
Plotkin, and Shannon obtained a deterministic distributed algorithm
coloring n-vertex planar graphs with 7 colors in O(logn) rounds. Here,
we show how to color planar graphs with 6 colors in polylog(n) rounds.
Our algorithm indeed works more generally in the list-coloring setting
and for sparse graphs (for such graphs we improve by at least one the
number of colors resulting from an efficient algorithm of Barenboim
and Elkin, at the expense of a slightly worst complexity). Our bounds
on the number of colors turn out to be quite sharp in general. Among
other results, we show that no distributed algorithm can color every
n-vertex planar graph with 4 colors in o(n) rounds. This is joint work
with Pierre Aboulker, Nicolas Bousquet and Louis Esperet.