$(\mathrm{\Delta }+1)$ Vertex Coloring in $O(n)$ Communication

We study the communication complexity of $(\mathrm{\Delta }+1)$ vertex coloring, where the edges of an $n$-vertex graph of maximum degree $\mathrm{\Delta }$ 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 $\mathrm{\Omega }(n)$ lower bound, this settles the randomized communication complexity of $(\mathrm{\Delta }+1)$-coloring up to constant factors.