On Edge Coloring Bipartite Graphs*
R. Cole
J. Hopcroft
TR 80--H443
Noveinber 1980
pepartment of Computer Science
Cornell University
Itha?a, New York 14853
*This research was supported in part by ONR grant N00014-76-C-0018.
TNTPflflIlCTTf)N
An algorithm for finding a minimal edge coloring of a bipartite graph in
time O(E log v) is presented. Polynomial time algoritlims for this problem have
previously been given by Gabow in [1] and by Cabow and Kariv in [2], the best
time bounds being OCE log2 v) and o(v2 log v).
The algorithin is based on using fast methods for finding
matchings in semiregular bipartite graphs; an algorithm for finding a
matching in a general bipartite graph was given by Hopcroft and
Two algorithms for finding such a matching are given. Although the
2
always has a faster running time of O(max(E, V log V log Dl), the
is presented for the sake of clarity.
?. NOTAn? Aflfl DEFINITIONS
maximal
maximal
in [3].
Karp
second one
first one
Throughout this paper G = (v,E) denotes a graph, V its vertex set and E
its edge set. G = (v11v2,E) denotes a bipartite graph with V1 and V2 being
disjoint vertex sets and E ? V1 * V2 being the edge set. D denotes the maximal
degree of any vertex in V = V1 u V2.
A graph is said to be regular if all its vertices have the same degree. A
bipartite graph is said to be semiregular if all the vertices in V1 have the
same degree D, the maximal degree of any vertex in G; it is said to be high-
low if there exists an integer k such that deg(v) ? k if v E V1 and deg(v) ? k
if v E V2.
An Euler partition is a partition of the edges into open and closed
paths, so that each vertex of odd degree is at the end of one open path, and
each vertex of even degree is at the end of no open paths.
An Euler split of a graph G = (V11v2,E) is a pair of graphs G1 -
(v1,V2*E1) and G2 = (v1,v21E2) where E1 and E2 are formed from an Euler
partition of E by placing alternate edges of each path into E1 and E2
respectively. Any vertex of even degree in G will have the same degree in both
G1 and G2, while any vertex of odd degree in G will have degrees in G1 and G2
differing by one. This implies that if G is semiregular, and D, the maximal
degree of any vertex in G is even, then both C1 and C2 are semiregular. An
algorithm for finding an Euler split in time 0(E) is given in [1].
?. ALGORITlIM ?
An o(E log
semiregular
into sets E1
v) time algorithm for finding a maximal matching in a
bipartite graph is given. The algorithm works by partitioning E
and E2 such that G1 = (v1,v2,E1) and G2 = (v1,v2,E2) are both
-2-
nontrivial seniregular bipartite graphs. If the graph with smaller edge set
has maximuni degree one it is the required matching; otherwise the algorithm is
applied recursively to that graph. Since each iteration reduces E by at least
a factor of two* the algorithm eventually terminates.
the semiregular graphs C1 and G2 is
giving graphs G1 and G2. If?D* the
even* then both C1 and G2 are
G1 and G2 to make them
The partitioning procedure to obtain
as follows. An Euler split of G is made
maximal degree of any vertex in C is
semiregular. Otherwise edges are moved between
semiregular. This is described more precisely below.
Let M be the set of ?aximuin degree vertices in G. At least half of
vertices in M will have even degree in one of C1 or G2. Without loss
generality let G2 be that graph in which at least half the vertices are
even degree. Then let M1 be those vertices of M that have even degree in
and 142 be the remaining vertices of 14.
Next
the
of
of
G2
an Euler split of G2 is made giving graphs G21 and G22. The
vertices of M1 have the same degree in G21 and G22* while some of the vertices
in 142 have even degree in G and odd degree in G and the others have odd
21			22
degree in G21 and even in G22; these degrees differ by one* and one of them is
the degree of the vertices of M1 in G21 (and in G22). Without loss of
generality let G22 be the graph in which at least half the vertices of ?2 have
even degree. Let M21 be the subset of vertices of 142 that have even degree in
C22 and let 1422 be the remaining vertices of 112.
Now one of the graphs G21 or G22 is combined with G1 in such a way that
vertices in 141 will have the same degree as vertices in ?2l in the combined
graph. The new graphs are named G1 and G2 in such a way that vertices in ?22
are of odd degree in G2. M1 and ?2 are redefined with N2 reduced in size by
at least a factor of two. The process is repeated until ?1 = 14 when the
vertices in 14 all have the same even degree in G1. The partitioning procedure
is shown in algol like form below.
-3-
PROCEDJIRE PARTITION
G = (V1E)
= set of maxirnum degree vertices of 0
BEGIN
END
Let G11 G2 be an Euler split of G;
At least half of the vertices in M have even degree in one of
G1 or 021 Let it be G2;
Let N1 = (viv E 141 and v has even degree in G2);
Let N2 =			--H M1;
`r?ILE (I?I2 ? 0) DO
BEGIN
END
Let G215 G22 be an Euler split of G22;
Again at least half the vertices in N2 have even degree in
either 021 or G221 Let it be G22;
Let 1121 = (viv E 1421 and v has even degree in G22);
Let 1122 = 112 --H ?21?
IF degree of a vertex in 111 in G22 is even
then
Cl := G1 u G211 G2 := 022
else
G2 := G1 U G22* G1 := G21;
111 := ?1 ? 11211 142 := M2?;
It is necessary to show that all the vertices in 111 have the same degree
in G1 at any given stage of the algorithm1 and likewise in G2. The same result
should be proven for vertices in 112. It will first of all be illustrated by an
example.
Consider the example in which vertices in 141 have degree 5 in Cl and
degree 12 in 021 while those in ?2 have degree 4 in Ci and degree 13 in 02.
Then vertices in 14i have degree 6 in both 021 and C?2; vertices in 1121
have degree 7 in 021 and degree 6 in C??; and vertices in ?22 have degree 6 in
021 and degree 7 in 022. So the assignments Cl = Cl U 0211 02 = 0221 ?i = 111
U 11211 and 1'2 = 11 are made.
22
Now vertices in 111 have degree 11 in Ci and degree 6 in 021 and vertices
in 112 have degree 10 in Cl and degree 7 in 02.
By considering respectively the cases in which the degree in Cl of
-4-
vertices in M1 is one greater or one lesser than that of vertices from 112 it
can be proven by induction that the degree of vertices in M1 is the same in
each of C1 and G2 and likewise for ?2. Thus all the vertices in M have the
same degree in each of G1 and 02 when the partitioning procedure terminates.
To show that G1 and G2 are both semiregular it is necessary to show that:
deg(v) in G15 v not in M < deg(v) in G15 v E M5 and similarly in G2.
This is proven by an induction using the inductive hypothesis that:
deg(v) in C15 v not in 14 ? deg(v) in G11 v E M15 and likewise in G2.
To show that both G1 and G2 are nontrivial the following inductive
hypothesis is proven:
deg of vertices of M1 in G2 > 0.
In fact this degree is even and so the degree of vertices from M1 in G21 and
G22 is nonzero. The induction now follows.
TTMING
Each iteration of the while loop reduces the size of 112 by at least a
factor of two. So after at most OClog v1) iterations I1!21 = 0 and the
procedure terminates. Each iteration of the while loop takes time 0(E). So to
obtain G1 and G2 takes time O(E log v1) < o(E log ElD). Thus the time T(E)
taken to find a matching is given by:
T(E) = o(E log E/D) + T(E/2) = O(E log ElD) s o(E log v).
In fact this algorithm will produce a matching covering all the vertices
of maximal degree in a general bipartite graph in time O(E log E/D).
A. ALGORTTHN ?
An o(E + V log V log2 D) time algorithm for finding a maximal matching in
a semiregular bipartite graph is given.
if a network has a maximal flow. with the flow through
then it has a maximal flow such that the flow
[4. pli3].
It is known that
each vertex being integral5
through each edge is integral
In particular5 if the edges of a bipartite graph are assigned positive
-5-
weights. so that the sum of the weights at each vertex is at most one. and the
weight at each vertex of V1 is one. then the graph has a taatching covering
every vertex of V1.
By
shifting the weights between edges. while maintaining a constant
weight at each vertex. and deleting edges of weight zero. a new smaller graph
is obtained containing just as large a matching.
Vertices of small degree are merged together so that all vertices have
degrees between D/2 and D. ?iow V*D 0(E). This simplifies the timing
analysis. Every edge is given weight lID. Using depth first search. cycles in
the graph among edges of weight lID are found. When a cycle is found alternate
edges in the cycle are deleted; the other edges in the cycle have their weight
doubled. This is continued until there are no cycles among edges of weight
lID. Cycles are then found among edges of weight 2/D. 4/D ..in turn until no
further increase in edge weights can be obtained in this way.
A graph with at most O(V log E/V) weighted edges is obtained. such that
the sum of the weights at each vertex in V1 is one. Algoritlin 1 is now
adapted to find this matching.
Each edge is considered to have multiplicity D times its weight . Four
copies of each edge are kept. one in each of C1. G2 G21 and G22. When making
an Euler split. each edge added to an Euler path is made to occur as often as
it can at that point in the path; the multiplicities of the copies of the edge
are changed accordingly. Otherwise one proceeds just as in algorithr:i 1.
As with algorithm 1 this algorithm can be used to find a matching
covering all the vertices of maximal degree in a general bipartite graph in
the same time bound.
One iteration of the procedure in algorithm 1 cuts
half (counting edges according to their multiplicity).
the size of the structure stored. affecting the timing
the number of edges in
but may well not reduce
given with algorithm 1.
To find the graph of size o(V log E/V). 0(E) time is needed. To use
algorithrn 1 one requires time o(v log E/V log E/D) to halve the number of
edges (counted according to their multiplicity). and time o(v log E/V log ElD
log D) = o(V log V log2 E/V) to obtain a t?ximal matching.
2
Thus the overall time taken is 0(E) for E ? O(Vlog V (loglog V)) and
--H6-
2
o(v log V log E/V) otherwise, which is always better than the O(E log v) of
algorithm 1.
?. COLORING ?iE EDGES QE ? RTPARTTTE GRAPii
An o(E log v) time algorithm for finding a minimal edge coloring is
given. It is minimal in the sense that the fewest possible colors are used. It
is shown in [1] that this is D colors.
The algoritbm is based on divide and conquer. When a graph has vertices
of even maximal degree, using the method of Euler partitions it is split into
two subgraphs of equal maximal degree which are then recursively colored. On
occasion when the graph has vertices of odd maximal degree a matching M
covering all the vertices of maximal degree has to be found. This is obtained
by using algorithm 2.
ALCORTTHM
If D is odd find a matching as described above; color it and delete it
from G. Set D = D - 1.
Make an ?uler split of G to give two bipartite graphs G1 and G2 each
having vertices of maximal degree D/2.
WLOC assume G1 has a smaller edge set than G2 (otherwise swap the labels
C1 and G2), and recursively color C1. Let 2 < D/2 = 2k+l - r. Add the r
smallest sets of colored edges to G2* delete them from the set of colored
edges, and recursively color G2.
A similar method was used in [3] and led to the current presentation of
the algoritb?n. That exactly D colors are used can be shown by induction.
TIi4TNG
Excluding the time taken to find the inatchings, the time taken is given
by:
T(E, D) = T(E1, LD/2J) + T(E2 u E3, LD/2J + r) + 0(E),
where E1 u E2 = E and E3 is the union of the r sets of colored edges added to
G2. For D a power of two T(E, D) = OCE log D). In all oU?er cases as 1E31 ?
2r 1E11/D ? E2l one finds that T(E, D) = O(2E log(D + r)) = O(E log D).
The time required for finding the matchings is bounded by O(max(E log- D,
V logv log3 D)) ? O(n?x(E log D, E log v)) and hence the total time required
is bounded by O(E max(log D, log v)) which is o(E log v). For a graph without
--H7--H
multiple edges a tiine bound of o(E max(log D, log v)) is obtained.
?. bIATCllINGS ? HIGlI LOW GRAPHS
the
By pruning high-low graph a semiregular graph with D = k can be
obtained, D being the maximal degree of any vertex in the semiregular graph.
The matching algorithm is then applied to this graph to obtain a inaxirnal
matching for the high-low graph. So a maximal matching in a high-low graph can
be found in time O(max(E, V log V log2 E/V)). High-low graphs were defined in
[3] and the above method for pruning was described there.
El] Cabow - Using Euler partitions to edge colour bipartite multigraphs, IJCIS
5,4.Dec 76.
[2] Gabow and Kariv - algorithins for edge colouring bipartite graphs and
multigraphs, SIGACT 78.
[3] Hopcroft and Karp - An n5?2 algorithm for maximal matchings in bipartite
graphs, S1A14 2,4,Dec 75.
[4] Lawler - Combinatorial Optimization, Networks and Matroids, Holt-
Rinehart-Winston.