446 Bor-Liang Chen,Ko-Wei Lih and Pou-Lin Wu have em+n-1.From the condition on y,we know that es3t+2(n-t).We obtain the result by combining these two inequalities. PRooF oF THEOREM 5.Let G be properly colored with three colors.The difference in sizes between the largest and the smallest color classes is called the width of the coloring.The coloring is equitable if the width is 0 or 1.We are going to show that,if the width of a coloring is at least 2,then we always can re-color some of the vertices to decrease the width. Let us start with the three color classes A,B and C,of sizes a,b and c,respectively, such that a≥b≥c and a-c≥2. (1)If there is a vertex x e A3B,then Cx will do.So from now on we assume that A3B=0. (2)Suppose that C3A=.Consider the bipartite subgraph G(A,C)induced by A and C.Since a=c+2 and A3B =☑，there must exist a component G(A',C')of G(A,C)such that A'>C'l.We have 0<A'-C1,by Lemma 6.Hence A']=IC'+1 and A'C'will decrease the width (3)Suppose that B3A=3.Let C3B=t.Similar to step (2),there must exist a component G(A',C')of G(A,C)such that A'>C'l.If IC'3A'st,then we have A'-C'l equal to some t'st+1,by Lemma 6.Choose a subset SC3B such that IS]=t'-1.Then A'C'US will decrease the width since C'and S are disjoint. If |C'3A'=t+1,then we consider the bipartite subgraph G(B,C)induced by B and C.We want to do some re-coloring so that B3A afterwards.If b=c,then BC suffices.Otherwise,since B>C and B3A=,there must exist a component G(B",C")of G(B,C)such that B">C".Since C"3B"C3B]=t,we have B IC"l equal to some t"s+1.Choose a subset S"C3A such that S"=t".Then B"C"US"will do,since C"and S"are disjoint. (4)Now our standing assumptions become A3B=，C3A≠☑andB3A≠⑦ If a=b,then Cx will decrease the width for any vertex xe B3A.Let a>b.If xeB3 4 and y∈A3C, then By and Cx will decrease the width.So we may assume that A3C =3.Then there must exist a component G(A',B')of G(A,B)such that IA'l>' Let B'3A'=and x E B3A.It follows from Lemma 6 that A'=B+1.Then Ccr and A'B'will decrease the width We may henceforth suppose that B'3A'.If there is some xE B'3A'such that one of its neighbors is y satisfying y A'1B',then By and Cx will decrease the width.Therefore,we may further assume that x E B'3A'and y e N(x)imply y eA'2B' for any x and y. Suppose that there are distinct,yB'3Ahaving intersecting neighborhoods.If Nx)=N(y),we first do an exchange B∈z and C←y for any z∈C3A.Then N(x)N(),since otherwise N(x)=N(y)=N(z)would force G=K3.3. This is impossible,since the chromatic number of G was assumed to be 3.So we may suppose that N(x)N(y).Let us choose we C3A and keep it fixed throughout the remaining argument. Now let u∈N(x)∩N(y).If u is not adjacent to w,then B←u,B←wand C,y}will decrease the width.If ue N(w)but there is a third ze B'3A',then u is not adjacent to z and B←w,C←u and C←z will decrease the width, It remains to handle two more cases:(i)every vertex in N(x)nN(y)is adjacent to w and B'3A'=fx,y);(ii)no two distinct x,y e B'3A'have intersecting neighborhoods In the former case,IN(x)UN(y)4 and 2 N(x)nN(y)1.From G(A',B'), delete B3Aand all those vertices which are adjacent to two vertices of BA'Then each remaining vertex will have degree 1 or 2.Hence the resulting graph G'(A',B')