Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
share
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(√(logΔ))+O(log^* n). In this paper, we study the edge coloring problem in the distributed LOCAL model. We show that the (degree+1)-list edge coloring problem, and thus also the (2Δ-1)-edge coloring problem, can be solved deterministically in time log^O(loglogΔ)Δ + O(log^* n). This is a significant improvement over the result of Kuhn [SODA '20].
READ FULL TEXT