Hardness of Minimal Symmetry Breaking in Distributed Computing
Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela · 2019
A graph is weakly 2-colored if the nodes are labeled with colors black and white such that each black node is adjacent to at least one white node and vice versa. In this work we study the distributed computational complexity of weak 2-coloring in the standard łocal model of distributed computing, and how it is related to the distributed computational complexity of other graph problems.