






















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 $\tilde{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 $\tilde 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。