  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 LOCAL model of distributed computing, and how it
is related to the distributed computational complexity of other graph problems.
First, we show that weak $2$-coloring is a minimal distributed
symmetry-breaking problem for regular even-degree trees and high-girth graphs:
if there is any non-trivial locally checkable labeling problem that is solvable
in $o(\log^* n)$ rounds with a distributed graph algorithm in the middle of a
regular even-degree tree, then weak $2$-coloring is also solvable in $o(\log^*
n)$ rounds there. Second, we prove a tight lower bound of $\Omega(\log^* n)$
for the distributed computational complexity of weak $2$-coloring in regular
trees; previously only a lower bound of $\Omega(\log \log^* n)$ was known. By
minimality, the same lower bound holds for any non-trivial locally checkable
problem inside regular even-degree trees.
