$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication

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