I will talk about the communication complexity of (Δ+1) vertex coloring, where the edges of an n-vertex graph of maximum degree Δ are partitioned between two players. I will show a randomized protocol which uses O(n) bits of communication and ends with both players knowing the coloring. Combined with a folklore Ω(n) lower bound, this settles the randomized communication complexity of (Δ+1)-coloring up to constant factors.
Based on joint work with Maxime Flin.
