$(\hat{I}”+1)$ Vertex Coloring in $O(n)$ Communication

Maxime Flin, Parth Mittal

We study the communication complexity of $(\hat{I}”+1)$ vertex coloring, where the edges of an $n$-vertex graph of maximum degree $\hat{I}”$ are partitioned between two players. We provide a…