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 $\hat{I}”$ can be properly edge colored with at most $\hat{I}”+1$ colors. In the online setting, it has been a matter of interest to fi…