(δ+1) Vertex Coloring in O(n) Communication

Abstract

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.