Round and Communication Efficient Graph Coloring

Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen +1

In the context of communication complexity, we explore protocols for graph coloring, focusing on the vertex and edge coloring problems in $n$-vertex graphs $G$ with a maximum degre…