Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
Alkida Balliu, Fabian Kühn, Dennis Olivetti · 2020
The problem of coloring the edges of an n-node graph of maximum degree Δ with 2Δ − 1 colors is one of the key symmetry breaking problems in the area of distributed graph algorithms. While there has been a lot of progress towards the understanding of this problem, the dependency of the running time on Δ has been a longstanding open question. Very recently, Kuhn [SODA '20] showed that the problem can be solved in time [EQUATION].