Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity

Leonid Barenboim, Michael Elkin, Tzalik Maimon

We consider coloring problems in the distributed message-passing setting. The previously-known deterministic algorithms for edge-coloring employed at least (2Delta - 1) colors, eve…