Distributed Edge Coloring in Time Polylogarithmic in Δ

Summary

Abstract. We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a [Formula: see text]-edge coloring can be computed in time [Formula: see text] in the [Formula: see text] model. This improves a result of Balliu, Kuhn, and Olivetti [ Distributed edge coloring in time quasi-polylogarithmic in [Formula: see text], in Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020, pp. 289–298], who gave an algorithm with a quasi-polylogarithmic dependency on [Formula: see text]. We further show that in the [Formula: see text] model, an [Formula: see text]-edge coloring can be computed in [Formula: see text] rounds. The best previous [Formula: see text]-edge coloring algorithm that can be implemented in the [Formula: see text] model is by Barenboim and Elkin [ J. ACM, 58 (2011), 23] and it computes a [Formula: see text]-edge coloring in time [Formula: see text] for any [Formula: see text].