Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

We consider the problem of maintaining a (1 + ϵ)∆-edge coloring in a dynamic graph G with n nodes and maximum degree at most ∆. The state-of-the-art update time is O ϵ (polylog(n)), by Duan, He and Zhang [SODA'19] and by Christiansen [STOC'23], and more precisely O(log 7 n/ϵ 2 ), where ∆ = Ω(log 2 n/ϵ 2 ).

The following natural question arises: What is the best possible update time of an algorithm for this task? More specifically, can we bring it all the way down to some constant (for constant ϵ)? This question coincides with the static time barrier for the problem: Even for (2∆ -1)-coloring, there is only a naive O(m log ∆)-time algorithm.

We answer this fundamental question in the affirmative, by presenting a dynamic (1 + ϵ)∆edge coloring algorithm with O(log 4 (1/ϵ)/ϵ 9 ) update time, provided ∆ = Ω ϵ (polylog(n)). As a corollary, we also get the first linear time (for constant ϵ) static algorithm for (1 + ϵ)∆-edge coloring; in particular, we achieve a running time of O(m log(1/ϵ)/ϵ 2 ).

We obtain our results by carefully combining a variant of the Nibble algorithm from Bhattacharya, Grandoni and Wajc [SODA'21] with the subsampling technique of Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC'22].