Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon · Society for Industrial and Applied Mathematics eBooks · 2024
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(log7 n/ɛ2), where Δ = Ω(log2 n/ɛ2).