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

Understand

We consider coloring problems in the distributed message-passing setting.

• The previously-known deterministic algorithms for edge-coloring employed at least (2Delta - 1) colors, even though any graph admits an edge-coloring with Delta + 1 colors [V64].
• Moreover, the previously-known deterministic algorithms that employed at most O(Delta) colors required superlogarithmic time [B15,BE10,BE11,FHK15].
• In the current paper we devise deterministic edge-coloring algorithms that employ only Delta + o(Delta) colors, for a very wide family of graphs.