Distance-2 Coloring in the CONGEST Model

We give efficient randomized and deterministic distributed algorithms for computing a distance-$2$ vertex coloring of a graph $G$ in the CONGEST model. In particular, if $Delta$ is the maximum degree of $G$, we show that there is a randomized CONGEST model algorithm to compute a distance-$2$ coloring of $G$ with $Delta^2+1$ colors in $O(logDeltacdotlog n)$ rounds. Further if the number of colors is slightly increased to $(1+epsilon)Delta^2$ for some $epsilon>1/{rm polylog}(n)$, we show that it is even possible to compute a distance-$2$ coloring deterministically in polylog$(n)$ time in the CONGEST model. Finally, we give a $O(Delta^2 + log^* n)$-round deterministic CONGEST algorithm to compute distance-$2$ coloring with $Delta^2+1$ colors.