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.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics