Distributed Algorithms for Near-Equitable Coloring

Amit Nir, David Peleg

For an $n$-vertex graph of maximum degree $\Delta$ and diameter $D$, an equitable $(\Delta +1)$-coloring is a vertex coloring where the frequency of each color (namely, the number of vertices…