A Fast Deterministic Algorithm for $(Δ+1)$-edge coloring in CONGEST
2026-08-19 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors study a classic problem about coloring the edges of a graph so that no two edges sharing a vertex have the same color, using one more color than the graph's maximum degree. Previous algorithms could do this efficiently in a distributed setting where nodes can send large messages (LOCAL model). The authors improve upon this by creating the first efficient deterministic algorithm that works even when nodes can only send small messages (CONGEST model). Their method matches the best known speed of the previous, less restrictive models, making it more practical for real networks.
Vizing's theoremedge coloringmaximum degreedistributed computingLOCAL modelCONGEST modeldeterministic algorithmgraph theoryround complexity
Authors
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin
Abstract
Vizing's theorem states that any graph of maximum degree $Δ$ can be properly edge-colored with $Δ+ 1$ colors (which is optimal in general). A recent breakthrough result by Bernshteyn showed that such a $(Δ+ 1)$-edge coloring can be found deterministically in $poly(Δ,\log n)$ rounds in the LOCAL model of distributed computing, where $n$ denotes the number of vertices of the input graph [J. Comb. Theory 2022]. Since then, the exponent in the $poly(\log n)$-part of the runtime has been improved by Christiansen [STOC 2023] and Bernshteyn and Dhawan [J. Comb. Theory, Series B, 2025]. However, the algorithms used in all of these works use large messages, leaving open the question for efficient algorithms in the more restrictive CONGEST model. We answer this question by presenting the first $poly(Δ,\log n)$-round algorithm for $(Δ+ 1)$-edge coloring in the CONGEST model. Our algorithm is deterministic and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.