Paper detail

Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta

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 long-standing open question. Very recently, Kuhn [SODA '20] showed that the problem can be solved in time $2^{O(\sqrt{\logΔ})}+O(\log^* n)$. In this paper, we study the edge coloring problem in the distributed LOCAL model. We show that the $(\mathit{degree}+1)$-list edge coloring problem, and thus also the $(2Δ-1)$-edge coloring problem, can be solved deterministically in time $\log^{O(\log\logΔ)}Δ+ O(\log^* n)$. This is a significant improvement over the result of Kuhn [SODA '20].