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 (2∆ − 1)-edge coloring can be computed in time poly log ∆ + O(log* n) in the LOCAL model. This improves a result of Balliu, Kuhn, and Olivetti [PODC '20], who gave an algorithm with a quasi-polylogarithmic dependency on ∆. We further show that in the CONGEST model, an (8 + ε)∆-edge coloring can be computed in poly log ∆ + O(log* n) rounds. The best previous O(∆)-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it computes a 2^{O(1/ε)}∆-edge coloring in time O(∆^ε + log* n) for any ε ∈ (0, 1].
2026-07-15
2026-05-04