Algorithms for Edge Coloring Bipartite Graphs

A minimum edge coloring of a bipartite graph is a partition of the edges into Δ matchings, where Δ is the maximum degree in the graph. Coloring algorithms are presented that use time O(min(¦E¦ Δ log n, ¦E¦ @@@@n log n, n 2 log Δ)) and space O(nΔ). This compares favorably to the previous O(¦E¦ [equation] log Δ) time bound. The coloring algorithms also find maximum matchings on regular (or semi-regular) bipartite graphs. The time bounds compare favorably to the O(¦E&brvbar @@@@n) matching algorithm, expect when [equation] ≤ Δ ≤ @@@@n log n.

Authors

• Harold N. Gabow
• Oded Kariv

Keywords

No keywords are indexed for this paper.