Edge-coloring bipartite graphs

Given a bipartite graph G with n nodes, m edges, and maximum degree a, we f ind an edge-coloring for G using a colors in time T + O(m log Delta), where T is the lime needed to find a perfect matching in a k-regular bipartite g raph with O(m) edges and k less than or equal to Delta. Together with best known bounds for T this implies on O(m log Delta + m/Delta log m/Delta log( 2)Delta) edge-coloring algorithm which improves on the O(m log Delta + m/De lta log m/Delta log(3)Delta) algorithm of Hopcroft and Cole. Our algorithm can also be used to find a (Delta + 2)-edge-coloring for G in time O(m log Delta). The previous best approximation algorithm with the same time bound needed Delta + log Delta. colors. (C) 2000 Academic Press.