Equitable coloring 447 decomposes into maximal paths.If all paths have initial and terminal vertices in different parts,then B'>A'l,which is a contradiction.Without loss of generality,let uo,v1,u2,v3,...,uzm be a maximal path of G'(A',B')such that wo is adjacent to B'3A'and u A'.If it is not the case that am N(y)for some y B'3A'and yx,then Cx together with A"B"will decrease the width,where A"= uA'and B"=vL,v3 B'.Suppose,on the other hand, thatN)N(y)and)N)for distinctandin adjacent to some v e A",then v is not adjacent to at least one of x and y,say y.Hence Bw and Cfv,y}will decrease the width.Otherwise,w is independent of A".Then B∈w,C∈{x,y}andA"台B"will decrease the width. We finally conclude that the width has been decreased in all cases and that the proof is complete. CoROLLARY 7.The equitable A-coloring conjecture holds for all connected graphs the maximum degree of which is at most 3. REFERENCES 1.B.Bollobas and R.K.Guy,Equitable and proportional coloring of trees,J.Combin.Theory,Ser.B,34 (1983).177-186 Bo and U.S.R. .Murty,Graph Theoryh Applications,Macmllan,London.96. o-0 quitablc co G.P Ko-Wei Lih, ing ot trees.C Combin.Theory,Ser.B.to appear. rac, orem abstract graphs.Proc.Lond ,Mah.Soc,2(1952),69-81: an eredi,Proof of a conjecture of Erdos,in:Combinatorial Theory and Its ions,Vol.Il,P.Erdos,A.Renyi and V.T.Sos(eds).Colloq.Math.Soc.Janos Bolyai 4,North Holland,Amsterdam,(1970),pp.601-623 6.Ko-Wei Lih and Pou-Lin Wu,On equitable coloring of bipartite graphs,Discr.Math.,to appear. 7.W.Meyer,Equitable coloring,Amer.Math.Monthly,80 (1973),920-922 Received 14 July 1993 and accepted 21 December 1993 Instinute of Applied Mathcmatics,Tunghai University,Taichung,Taiwan 40704 Ko-WEI LIH Institute of Mathematics,Academia Sinica.Nankang.Taipei,Taiwan /1529 POU-LIN WU Department of Mathematics,Louisiana State University,Baton Rouge,LA 70803,U.S.A