Dynamic Edge Coloring with Improved Approximation
Ran Duan, Haoqing He, Tianyi Zhang · Society for Industrial and Applied Mathematics eBooks · 2019
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(log8 n/∊4) amortized update time when Δ ≥ Ω(log2 n/∊2), where ∊ > 0 is an arbitrarily small constant.