On Edge Coloring Bipartite Graphs
Original Publication Date: 1980-Nov-30
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Cole, R.: AUTHOR [+3]
On Edge Coloring Bipartite Graphs* R. Cole J. .Hopcroft
On Edge Coloring Bipartite Graphs*
Department of Computer Science Cornell University
Ithaca, New York 14853
*This research was supported in part by ONR grant N00014-76-C-0018.
An algorithm for finding a minimal edge coloring of a bipartite graph in t h e o(E log V) i s presented. Polynonial time algoritlms for this problem have previously teen given by Gabow in [l] and by Gabow snd Kariv in , the best
tine bounds being O(E log2 V) and O(V log V).
The algorithm is based on using fast methods for finding maximal matchings in semircgular bipsrtite graphs; a11 algorithm for finding a maximal natching in a general bipartite graph was given by Hopcroft and Karp in C33. Two algoritlms for finding such a nstching are given. Although the second one aluays has a faster running time of O(naxiE, V log V log2 Dl), the f i r s t one i s presented for the sake of clarity.
Throughout this paper G = (V,E) denotes a graph, V i t s vertex set and E its edge set. G = (v1,v2,E) denotes a bipzrtite graph with V1 and V2 being disjoint vertex sets and E C V1 * V2 being the edge set. D denotes the maximal degree of any vertex i n V = V1 u V2.
A graph i s said to be regular if a l l its vertices have the same degree. A bipartite graph i s said to be semiregular if a l l the vertices i n V have the
scme degree D, the maximal degree of any vertex i n G; it i s said to be high- low if there exists an integer k such that deg(v) 2 k if v E V1 and deg(v) 5 k if v E V2.
An Euler partition i s a partition of the edges into open and closed paths, so that each vertex of odd degree is; a t the end of one open path, and each vertex of even degree i s at the end of no open paths.
An Euler split of a graph G = (Vl.V2.~) is a pair of graphs G1 -
- ( v ~ , v ~ . E ~ )
and G2 = ( v ~ , v ~ . E ~ )
where El and E2 are formed from an Euler
partition of E by placing alternate edges of each path into El and E2 respectively. Any vertex of even degree i n G w i l l have the same degree i n both G1 and G2, while any vertex of odd degree in G w i l l have degrees in G1 and G2
differing by one. This implies that if G is semireg~lar. and D, the maximal degree .of any vertex in G is even, then both G1 and G2 are semiregular. An algoritim for finding an Euler s p l i t i n time O(E) is given i n C11.
An O(E log V) tine algorithm for finding a maximal matching in a seniregular bipartite graph i s given. The algorithm works by partitioning E into sets El and E2 such that G1 = (V1,V2,EI) and G2 = (V 1 2 2
,V ,E ) are both
izontrivial sailiregular bipartite graplis. If the graph with smaller edge set has rilaxi~~ur,~