2024/04/29 by Maxime Flin, Flin, Maxime, Parth Mittal +1
Engineering · #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2404.19081
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.