$(\hat{I}”+1)$ Vertex Coloring in $O(n)$ Communication

Abstract

We study the communication complexity of $(\hat{I}”+1)$ vertex coloring, where the edges of an $n$-vertex graph of maximum degree $\hat{I}”$ are partitioned between two players. We provide a randomized protocol which uses $O(n)$ bits of communication and ends with both players knowing the coloring. Combining this with a folklore $\hat{I}\text{c◯}(n)$ lower bound, this settles the randomized communication complexity of $(\hat{I}”+1)$-coloring up to constant factors.

Updated to match Distributed Computed Journal version. (18 pages, 1 figure)