View PDF HTML (experimental)

Abstract:As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors any $n$-node graph with maximum degree $\Delta$ with with $(1+\varepsilon)\Delta+O(\sqrt{\log n})$ colors in $\tilde{O}(\log^{2.5} n+\log^2 \Delta \log n)$ rounds. This brings the upper bound polynomially close to the lower bound of $\Omega(\log n/\log\log n)$ rounds that also holds in the more powerful LOCAL model [Chang, He, Li, Pettie, Uitto; SODA'18]. As long as $\Delta \geq c\sqrt{\log n}$ our algorithm uses fewer than $2\Delta-1$ colors and to the best of our knowledge is the first polylogarithmic-round CONGEST algorithm achieving this for any range of $\Delta$.
As a corollary we also improve the complexity of edge coloring with $2\Delta-1$ colors for all ranges of $\Delta$ to $\tilde{O}(\log^{2.5} n+\log^2 \Delta \log n)$. This improves upon the previous $O(\log^8 n)$-round algorithm from [Fischer, Ghaffari, Kuhn; FOCS'17].
Our approach builds on a refined analysis and extension of the online edge-coloring algorithm of Blikstad, Svensson, Vintan, and Wajc [FOCS'25], and more broadly on new connections between online and distributed graph algorithms. We show that their algorithm exhibits very low locality and, if it can additionally have limited local access to future edges (as distributed algorithms can), it can be derandomized for smaller degrees. Under this additional power, we are able to bypass classical online lower bounds and translate the results to efficient distributed algorithms. This leads to our CONGEST algorithm for $(1+\varepsilon)\Delta+O(\sqrt{\log n})$-edge coloring. Since the modified online algorithm can be implemented more efficiently in the LOCAL model, we also obtain (marginally) improved complexity bounds in that model.

Submission history

From: Tijn De Vos [view email]
[v1] Tue, 3 Mar 2026 07:32:48 UTC (219 KB)
[v2] Wed, 19 Aug 2026 10:30:40 UTC (209 KB)