Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs

Aditi Dudeja, Rashmika Goswami, Michael Saks

Vizing's theorem states that any graph of maximum degree $\Delta$ can be properly edge colored with at most $\Delta +1$ colors. In the online setting, it has been a matter of interest to find…