Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
Aditi Dudeja, Rashmika Goswami, Michael Saks · Society for Industrial and Applied Mathematics eBooks · 2025
Vizing’s theorem states that any graph of maximum degree Δ can be properly edge colored with at most Δ +1 colors. In the online setting, it has been a matter of interest to find an algorithm that can properly edge color any graph on n vertices with maximum degree Δ = ω (log n ) using at most (1 + ο (1))Δ colors. Here we study the naive random greedy algorithm, which simply chooses a legal color uniformly at random for each edge upon arrival. We show that this algorithm can (1 + ϵ ) Δ-color the graph for arbitrary ϵ in two contexts: first, if the edges arrive in a uniformly random order, and second, if the edges arrive in an adversarial order but the graph is sufficiently dense, i.e., n = Ο (Δ). Prior to this work, the random greedy algorithm was only known to succeed in trees.