Abstract:
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].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 2O(log2 log Δ)+O(log* n). This is a significant improvement over the result of Kuhn [SODA ’20].
