Richard Cole, Kirstin Ost
Let V, E, and D denote the cardinality of the vertex set, the cardinality
of the edge set, and the maximum degree of a bipartite multigraph G.
We show that a minimal edge-coloring of G can be computed in O(E log D)
time. This result follows from an algorithm for finding a matching
in a regular bipartite graph in O(E) time.