Yannic Maus (co-authors Mohsen Ghaffari, Fabian Kuhn and Jara Uitto)
Title: Deterministic Distributed Edge-Coloring with Fewer Colors

Abstract: 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
\Delta=\tilde{\Omega}(log n) For smaller ,we give a
polylogarithmic-time (3/2+o(1))-edge-coloring. These are the first
deterministic algorithms to go below the natural barrier of (2
\Delta-1) colors, and they improve significantly on the recent
polylogarithmictime (2+o(1))\Delta)-edge-coloring of Ghaffari and Su
[SODA’17] and the (2\Delta- 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.