Let V, E, and D denote the cardinality of the vertex set, the edge
set, and the maximum degree of a bipartite multigraph G. We show that
a minimum edge-coloring of G can be computed in O(E log D) time. This
result is based on an O(E) time algorithm to compute a matching in
a regular bipartite graph.