A simple algorithm for edge-coloring bipartite multigraphs

Noga Alon

doi:10.1016/S0020-0190(02)00446-5

A simple algorithm for edge-coloring bipartite multigraphs

Noga Alon

Research output: Contribution to journal › Article › peer-review

46 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 language	English (US)
Pages (from-to)	301-302
Number of pages	2
Journal	Information Processing Letters
Volume	85
Issue number	6
DOIs	https://doi.org/10.1016/S0020-0190(02)00446-5
State	Published - Mar 31 2003
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Edge-coloring
Graph algorithms

Access to Document

10.1016/S0020-0190(02)00446-5

Cite this

@article{6179d5ae9a394d2982f98138ac43a4b6,

title = "A simple algorithm for edge-coloring bipartite multigraphs",

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.",

keywords = "Edge-coloring, Graph algorithms",

author = "Noga Alon",

note = "Funding Information: E-mail address: [email protected] (N. Alon). 1 Research supported in part by a USA–Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.",

year = "2003",

month = mar,

day = "31",

doi = "10.1016/S0020-0190(02)00446-5",

language = "English (US)",

volume = "85",

pages = "301--302",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - A simple algorithm for edge-coloring bipartite multigraphs

AU - Alon, Noga

N1 - Funding Information: E-mail address: [email protected] (N. Alon). 1 Research supported in part by a USA–Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

PY - 2003/3/31

Y1 - 2003/3/31

N2 - 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.

AB - 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.

KW - Edge-coloring

KW - Graph algorithms

UR - http://www.scopus.com/inward/record.url?scp=0037475041&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037475041&partnerID=8YFLogxK

U2 - 10.1016/S0020-0190(02)00446-5

DO - 10.1016/S0020-0190(02)00446-5

M3 - Article

AN - SCOPUS:0037475041

SN - 0020-0190

VL - 85

SP - 301

EP - 302

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

A simple algorithm for edge-coloring bipartite multigraphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this