Unfriendly colorings of graphs with finite average degree

Abstract

In an unfriendly coloring of a graph the color of every node mismatches that of the majority of its neighbors. We show that every probability measure preserving Borel graph with finite average degree admits a Borel unfriendly coloring almost everywhere. We also show that every bounded degree Borel graph of subexponential growth admits a Borel unfriendly coloring.

6 pages

References in corpus (1)

• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs

Cited by in corpus (1)

• Distributed Algorithms, the Lovász Local Lemma, and Descriptive Combinatorics