Self-Stabilizing Algorithms for Unfriendly Partitions Into Two Disjoint Dominating Sets

An unfriendly partition is a partition of the vertices of a graph G = (V,E) into two sets, say Red R(V) and Blue B(V), such that every Red vertex has at least as many Blue neighbors as Red neighbors, and every Blue vertex has at least as many Red neighbors as Blue neighbors. We present three polynomial time, self-stabilizing algorithms for finding unfriendly partitions in arbitrary graphs G, or equivalently into two disjoint dominating sets.