A simple algorithm for edge-coloring bipartite multigraphs was presented. The chromatic index of any bipartite multigraph (G) with (n) vertices and (m) edges is equal to its maximum degree (k). A perfect matching in G in time O(nk + n logk log(nk)), was found by the corollary. The proof of corollary provided a proof of the marriage theorem for regular bipartite multigraphs using Euler's theorem.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
- Graph algorithms