Dynamic Edge Coloring with Improved Approximation

Given an undirected simple graph G = ( V, E ) that undergoes edge insertions and deletions, we wish to efficiently maintain an edge coloring with only a few colors. The previous best dynamic algorithm by [3] could deterministically maintain a valid edge coloring using 2Δ – 1 colors with O (log Δ) update time, where Δ stands for the current maximum vertex degree of graph G. In this paper, we first propose a new static (1 + ∊ )Δ edge coloring algorithm that runs in near-linear time. Based on this static algorithm, we show that there is a randomized dynamic algorithm for this problem that only uses (1 + ∊ )Δ colors with O (log 8 n / ∊ 4 ) amortized update time when Δ ≥ Ω(log 2 n / ∊ 2 ), where ∊ > 0 is an arbitrarily small constant.

Authors

• Ran Duan
• Haoqing He
• Tianyi Zhang 0008

Keywords

No keywords are indexed for this paper.