2 papers
cs.DC2026
Diameter-Free Distributed Frequency Control for Graph Coloring in the CONGEST Model
Amit Nir, David Peleg
This paper presents two randomized proper-coloring algorithms that control color frequencies in the synchronous CONGEST model without paying a diameter-dependent coordination cost.…
cs.DC2026
Distributed Algorithms for Near-Equitable Coloring
Amit Nir, David Peleg
For an -vertex graph of maximum degree and diameter , an equitable -coloring is a vertex coloring where the frequency of each color (namely, the number of vertices…