Deterministic distributed edge-coloring with fewer colors

We present a deterministic distributed algorithm, in the LOCAL model, that computes a (1+ o (1))Δ-edge-coloring in polylogarithmic-time, so long as the maximum degree Δ=Ω(log n ). For smaller Δ, we give a polylogarithmic-time 3Δ/2-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of 2Δ−1 colors, and they improve significantly on the recent polylogarithmic-time (2Δ−1)(1+ o (1))-edge-coloring of Ghaffari and Su [SODA’17] and the (2Δ−1)-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS’17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes.

Authors

• Mohsen Ghaffari 0001
• Fabian Kuhn
• Yannic Maus
• Jara Uitto

Keywords

• Vizing's Theorem
• deterministic
• distributed computing
• edge-coloring
• matching
• matching approximation