Browse Prior Art Database

On Edge Coloring Bipartite Graphs

IP.com Disclosure Number: IPCOM000148360D
Original Publication Date: 1980-Nov-30
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Cole, R.: AUTHOR [+3]

Abstract

On Edge Coloring Bipartite Graphs* R. Cole J. .Hopcroft

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 23% of the total text.

Page 1 of 10

On Edge Coloring Bipartite Graphs*

R. Cole
J. .Hopcroft

November 1980

Department of Computer Science Cornell University
Ithaca, New York 14853

*This research was supported in part by ONR grant N00014-76-C-0018.

[This page contains 1 picture or other non-text object]

Page 2 of 10

[This page contains 1 picture or other non-text object]

Page 3 of 10

    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 [2], the best

2

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

1

-

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

[This page contains 1 picture or other non-text object]

Page 4 of 10

izontrivial sailiregular bipartite graplis. If the graph with smaller edge set has rilaxi~~ur,~
degree...