Edge-Coloring Algorithms for Bounded Degree Multigraphs

Abhishek Dhawan

In this paper, we consider algorithms for edge-coloring multigraphs $G$ of bounded maximum degree, i.e., $\Delta (G)=O(1)$. Shannon's theorem states that any multigraph of maximum degr…