$(\Delta +1)$ Vertex Coloring in $O(n)$ Communication

Maxime Flin, Parth Mittal

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 ra…