We give an efficient (polylog(n) rounds) algorithm that colors a graph with few colors in the distributed setting (LOCAL model). Among other things, we will see that this algorithm 6-colors planar graphs (using 1 less color than the previous best algorithm of Goldberg, Plotkin, and Shannon) and will show that one cannot 4-color planar graph in o(n) rounds.

This is a joint work with Bousquet, Bonamy, and Esperet.