2023/11/14 by Bhattacharya, Sayan, Costa, Martín, Panski, Nadav +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.08367
The problem of edge coloring has been extensively studied over the years. Recently, this problem has received significant attention in the dynamic setting, where we are given a dynamic graph evolving via a sequence of edge insertions and deletions and our objective is to maintain an edge coloring of the graph. Currently, it is not known whether it is possible to maintain a (Δ+ O(Δ1 - μ))-edge coloring in O(1) update time, for any constant μ> 0, where Δ is the maximum degree of the graph. In this paper, we show how to efficiently maintain a (Δ+ O(α))-edge coloring in O(1) amortized update time, where α is the arboricty of the graph. Thus, we answer this question in the affirmative for graphs of sufficiently small arboricity.