(Δ + 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.