THE UN I VE RS I TY 0 F M I CH I GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report How to Color the Lines of a Bigraph Dennis P. Geller with assistance from: Department of Health, Education, and Welfare National Institutes of Health Grant No. GM-,12236 Bethesda, Maryland and National Science Foundation Grant No. GJ-519 Washington, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR April 1971

Ist FXSs

ABSTRACT It is shown that the lines of any bigraph G can be colored from (B1''",**AI A is the maximum of the degrees of the points of G) in such a way that all lines colored from {Bj jjd} are incident with points of degree at least d.

Konig [2] showed that the lines of any bigraphl G can be colored from a set O{1'"'' lA}A in such a way that no two lines which are assigned the same color are adjacent, where A = A(G) is the maximum of the degrees of the points in G. It is then natural to conjecture that a bigraph G should have a line-coloring in which the only lines colored BA are incident with points of degree A. This is indeed true; in this paper we prove the following stronger result: Theorem 6: Let G be a bigraph with degree sequence dl<d2<...<dr = A. Then G has a line-coloring from {B1,.,B}A} such that all lines colored Bd.+l,-..,d i i+l are incident to points of degree at least di+l. Before we begin proving the theorem,we present some convenient notation and definitions. If in some line-coloring of G a line x = uv is colored with a we say that x is an a-Line; we also say that a appears at both u and v. If a and B are two colors used in a line-coloring of G then by GJBa we mean that subgraph of G induced by the lines colored a or S. In any bigraph G, we will let V1 and V2 stand for the blocks of the partition of the point set of G. Theorem 1: Let G be a bigraph such that all points of maximum degree are in V2. Then G can be line colored from 0{1' ***'A} such that the only lines colored BA are incident with points of maximum degree. Proof: We suppose the result to be true for bigraphs with q-l lines. 1Definitions not given here can be found in [1].

Let G have q lines and let all points of maximum degree be in V2; let x = uv be incident with one such point v. If A(G-x) < A(G) = A then v was the only point of maximum degree in G. So any line-coloring of G-x from {1,.'. S 1} extends to a line-coloring of G in which only x is colored aA. If A(G-x) = A(G) = A then we can color G-x with A colors so that all lines colored A are incident with points of maximum degree; in particular, no line colored Sa is incident with v. If there is no aA-line at u, then x can be colored SA in G. Otherwise, there is a BA-line uvl [where deg vl = A]. Since deg u < A there is some color a which does not appear at u. Clearly however, there is a line v u1 colored a. Thus we get a sequence <u = u0,Vl,ul,v2,... > such that each vi has maximum degree, each ujvj+1 is colored SB and each v.u. is colored a. Since deg v = a, the process cannot stop with a vj, so it must stop at some uj, at which there is no SA-line. We have thus defined a component of the subgraph G-xja,, and can interchange the colors a and BA in this subgraph, preserving the validity of the coloring. But now SA does not appear at u, so x can be colored with a. Theorem 2: In a bigraph G, suppose max {deg uluEV1} = n and that there are at least two degrees greater than or equal to n realized by points of V2, the two largest being n < A' < A. Then there is a line-coloring of G from A{1,'...'b} such that all lines colored aA,+l,...,BA are incident with points of maximum degree. Proof: Clearly the result is true whenever n=l. Suppose it to be true for n-l, and suppose that in G, max{deg ulueV1 = n. Note that if A-A' = 1 then the result holds by Theorem 1.

Suppose now that the result is true for A-A' = t-l, and that in G, A-A' = t, where v1,...,vr are the points of degree A. We remove an independent set X of r lines, one adjacent to each of vl,..,V r, to get G':A(G') = A(G)-l. If, in G', max {deg ulueV1} = n then G' can be colored with A(G)-l colors in the prescribed manner: the only lines colored A,+i, A...,BA_ are incident with the vr. Now, the lines of X can be colored 8. Otherwise, max {deg ulueV1} = n-l. By induction on n, a line-coloring of G' with the desired properties can be achieved, and this coloring uses only A-1 colors, as above. Again, the lines of X can be colored B.A Theorem 3: Let G be a bigraph in which max {deg ulueV1} = n, A(G) = A > n, and suppose there are no points of degree n+l,...,A-l. Then G has a line-coloring from {1,...,SA} such that all lines colored 8n+1l,'BA are incident with points of maximum degree. Proof: By Thcorcm 1 we know the result is true, for any n, if A = n+!. Also, the result is trivially true whenever n=l. Suppose that the result holds when max {deg u1uEV1} = n-l, and let G have max {deg uJluV1} = n. Since we know the result holds for A = n+l suppose that it holds for A = n+k-l, and let G have A(G) = A = n+k. Suppose the points of degree A are vl,...,v. Remove an independent set X of lines which covers {v1,..,vr}, and let G-X = G'. If in G', max {deg uluEV1} = n then the resulting graph satisfies the conditions of the theorem with A = n+k-l, so there is a line-coloring where all lines colored Sn+l.'.n+k 1 are incident with the v.. Then the lines in X can be colored a and the result holds. n+k Otherwise, in G', max {deg ulueV1} = n-l. Then the result holds for ( I);' iyl(liCtci o tlU Io.:;s tlhUro woro poi its of (deGeo n in V,. I1 so, (;' satisfies the conditions of Theorem 2 with A'(G') = n, A(G') = A-1, and

so there is a line-coloring of G' from {0,.o. $ A_1 } such that all lines colored AI'+1 = 8n+l''BOA-1 are incident with the vi. By coloring the lines of X with 8A the result holds. If V2 had no points of degree n, then by the inductive hypothesis [induction on n], in the line-coloring of G' all lines colored 8n,$n+l.'%_1 are incident with the vi. We can again color the lines of X with a., proving the theorem. Theorem 4: Let G be a bigraph in which max {deg ulueV1} = n = do, and suppose that the degrees greater than n which are realized in V2 are n<dl<d2<...<dr = A. Then there is a line coloring of G from 0{1.tA} such that all lines colored 8d +l...,Sd i i+l are incident to points of degree greater than di, for i = O,...,r-l. Proof: The result is trivial for n=l. Also, by Theorem 3, it holds whenever r=l, so we can assume it true for bigraphs in which max {deg ulueV } s n-l and also for bigraphs in which max {deg uueV} = nII and r-l degrees greater than n are realized in V2. Let G have max {deg ujusV } = n and let degrees n<dl<..<dr = A be realized in V2. We first prove the result in the case d -d = 1. Suppose we remove an independent set X covering the points of degree dr, to get a graph G'. If the maximum degree of the points in V1 is reduced to n-l, then G' has a line-coloring of the desired type; in particular, all lines colored B Sd...d are incident with points of degree d in G', those being r-2 r-l the points of degree dr-1 or dr in G. Then by coloring the lines of X with 8A, the desired coloring results. If in G' the maximum degree of the points in V1 is n, then the inductive hypothesis on r guarantees the desired coloring for G', and again we can color the lines of X with B.

Now, suppose the result holds for dr - dr = t-l and suppose that, in G, dr - dr-1 = t. Let v,...,v5 be the points of degree dr = A. We can remove an independent set of lines X which covers {vl,..,v }, giving a graph G' with maximum degree A-1, and next largest degree dr1; note that (A-1) - d1 = t-l. If, in G', max {deg ulueV1} = n we get a line coloring of G' from {i1...'SA_1 with the desired properties by the inductive hypothesis on t. If not, we get a line-coloring by the inductive hypothesis on n. Either way, we can color the lines of X with SA* Theorem 5: Suppose G is a bigraph and that there are points of degree A(G) = A in both V1 and V2. Then G has a coloring from {B1,, } such that all lines colored 8^ are incident with points of degree A. Proof: Assume that the result holds for bigraphs with at most q-l lines and let G have q lines. Suppose uEV1 has deg u = A and that v is a point with deg v < A such that x = uv is a line of G. Let G' = G-x. Clearly A(G') = A, for G had points of degree A in both V1 and V2. There are then two cases to consider. Case I: In G' there are points of degree A in both V1 and V2. We apply the inductive hypothesis to get a line coloring of G' such that each 3A-line is incident to a point of degree A. If neither u nor v is incident with a BA-line, we can color x with 8A in G. Suppose first there is a aA-line vu1 at v. We choose a color a which does not appear at v and form the sequence <v0 = v,ul,vl,U2,v2,...> where each line viui+1 is colored BA and each line u.vi is colored a. The process defines a component of G' |aB and we can interchange a and gA so that there is now no BA-line at v. Note that this procedure cannot introduce a BA line at u. If u is a point ui

then there is already a line Vilu colored 3A: it may however happen that as a result of the process there is no B- line at u. In any event, if there is now no SA-line at u we can color x with BA in G. So suppose uv1 is a SA-line at u. Since in G' deg u = A-1 there is a color 6 which does not appear at u. If it is also true that 6 does not appear at v then by the same procedure we can replace the Sk-line at u with a 6-line at u, without reintroducing a BA-line at v, and then x can be colored with BA in G. Otherwise, if 6 appears at v, since in G' deg v < A-2 there is some color y # BA which does not appear at v, and 6 can be replaced by y at v. This replacement does not alter the set of colors at u. We now have the situation where color 6 appears at neither u nor v. Then as noted, we can recolor the aA-line at u by 6, and then, in G, x can be colored with A'. Case II: In G' there are no points of degree A in V1. We can now apply Theorem 1 and color the lines of G' in such a way that all lines colored aB are incident to points of maximum degree. Since there are no points with degree A in V1 we know that there is no aA-line at v. If there is also no BA-line at u, we can color x with 8A in G. Otherwise, as above, we choose a color a which does not appear at u and interchange %A with a. Then x can be colored with Ba. It may, however, have been the case that in G, every point of degree A was adjacent only to other points of degree A. But then, for each point u with degree A, the component of G containing u is the complete bigraph KiA for which the result certainly holds. Suppose that G is a bigraph such that there are points of maximum degree in both V1 and V2. Color the lines of G in the manner prescribed

by the theorem, and let X1 be the set of lines colored 8A. If G1 = G-X1, then A(G1) = A-l, there are points of degree A-1 in both V1 and V2, and G1 has a line-coloring from {B1,., A1} such that all lines colored BAl1 are incident with points of degree A-1. The line-coloring of G1 clearly extends to G; since X1 was an independent set of lines, all the lines in X1 can be colored %A. Thus G has a line-coloring from {B1... SA} such that all lines colored 8A are incident with points of degree A and all lines colored $A-1 are incident with points of degree A-1 or A. But the procedure we have outlined applies to G1: we can remove the set X2 of lines colored A-1 resulting in a bigraph G2 in which points of maximum degree appear in both V1 and V2 giving rise to a line-coloring of G in which all lines colored BAi are incident to points of degree at least A-i for i = 0,1,2. The process clearly extends further. We have thus proved. Corollary: Let G be a bigraph in which there are points of degree dl<d2<..<dr = A, and such that both V1 and V2 have points of degree A. 1hen 2'' rh 1s ei od ree Then G has a line coloring from {1',..''A} such that all lines colored,k>dj, are incident to points of degree at least dj+l, for j = 1,2,...,r-1. We can now apply the procedure used to prove the Corollary to bigraphs in which points of maximum degree appear only in, say, V2. At each stage we remove an independent set of lines and lower the maximum degree by 1. If at some step we arrive at a bigraph in which there are points of maximum degree in both V1 and V2, we apply the Corollary. Otherwise, the procedure terminates when all points in V1 have degree one or zero, we can then apply Theorem 4. We have thVs proved: Theorem 6: Let G be a bigraph in which there are points of degree dl<d2<...<d = A. Then G has a line-coloring from B1...,'"A} such that 1 2 r

all lines colored ~d'i' d arel i+l are incident with points of degree at least di+.

REFERENCES 1. Harary, F. Graph Theory, Addison-Wesley, Reading, 1969. 2. Kinig, D. Theorie der Erdlichen und Undendlichen Graphen, Chelsea, New York.

UNIVERSITY OF MICHIGAN 3I IIIIIII 0 llll1115 110282 9IliiJi l 3 9015 02825 9656