A simple algorithm for edge-coloring bipartite multigraphs

Research output: Contribution to journalArticle

41 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)301-302
Number of pages2
JournalInformation Processing Letters
Volume85
Issue number6
DOIs
StatePublished - Mar 31 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Edge-coloring
  • Graph algorithms

Fingerprint Dive into the research topics of 'A simple algorithm for edge-coloring bipartite multigraphs'. Together they form a unique fingerprint.

  • Cite this