Fast algorithms for Vizing's theorem on bounded degree graphs

Anton Bernshteyn, Abhishek Dhawan

Vizing's theorem states that every graph $G$ of maximum degree $\hat{I}”$ can be properly edge-colored using $\hat{I}”+1$ colors. The fastest currently known $(\hat{I}”+1)$-edge-coloring algorithm…