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