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 $\Delta$ can be properly edge-colored using $\Delta +1$ colors. The fastest currently known $(\Delta +1)$-edge-coloring algorithm for…