Distributed Edge Coloring in Time Polylogarithmic in \({\Delta }\)

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].