圣 Bor-Liang Chen.Ko-Wei Lih and Pou-Lin Wu of vertices in B into red.A one-way arrow AB means that we change the color of B into the A B=ixh and an ind that ea h vertex of I is adjacent to all vertices of H.The complement graph of G is denoted by G. 2.GRAPHS WITH HIGH DEGREES LEMMA 1. Let G be a discon graph.If G is different from (K)and (Knm+2m+y for all m≥1，hcna'(G)>8G. PROOF.Let G,G2,.,G,t≥2，be the components of G.Ifδ(G)=0or 8(G)=1,then the lemma clearly holds.Suppose that 8(G)=2,and hence 8(G)=2 for all i. Consider a longest path in G,and the vertices adjacent to the initial vertex of this path.We see ediately that G contains a cycle of length at least 8(G)+1.(This ment was first ed in Dirac [41.)Thus aG)≥(8(G)+1)/2J≥L(8(G)+1)/2 It ol that a ( G)unless '(G2)-[(a(G)+1)/2]for an even 8(G)- 2m We want to show that this case would force the graph to become (K2+1+).Let x1,x2,...,xam+be a cycle of length 2m +1 in G.If there is an edge uv such that u or v is different from all the x,'s,then a'(G)m+1,which is false.It follows that r,.r,. ..,xm is precisely the vertex set of G.Since the degree of every vertex is at least 2m,G is a copy of Kzm Similarly,G2 is another copy of K2m+1 Hence G turns out to be a(K),which is excluded from the assumptions. LEMMA 2.Let G be nected graph such that G>28(G)+1.If G is not (G)-splittable,then a'(G)>(G). PRooF.For a connected graph G,G>2(G)is sufficient to guarantee the existence of a path P={xo,x1, .x28}of length 28=28(G)(see [2,Exercise 4.2.9)). Hence a'(G)≥6(G). hepah"2zoncpaSlyaMGdeneniahgote8oltynemh the path tside of the path P.The existe follow 1G1>28(G)+1 from the that If y were any x0x23 1x2Y,x2+1x2+2 x2s-x2s would form a mat ing of size However,since the degree of y is at least ,ymust be adja +1,a contradiction to allx2+1,0si<8.Now suppose that x2 and x2y,i j,are adjacent.Then x0r1,,·,,X2/-22-1;X2+2X2+3,·.·,X2-2X2-1;X2+1X2+2,.··,X28-1X28;X2X2iX2i+1y} would form a matching of size +1.So 1=V(G)-(x1,x3,....,x2 is an independent set and each vertex in I is adjacent to all x2s+1,0si<8,i.e.G is 8(G)-splittable.This shows that a'(G)=8(G)could not occur. ■ THEOREM 3.Let G be cted with A(G)G If G is diferent from K and all m1,then G is equitably A(G)-colorable PROOF.Since 4(G)+8(G)=IG]-1 and 4(G)GI/2,we have G>28(G)+1. If G is disconnected,then a'(G)>(G),by Lemma 1.Since G is connected,G cannot be 8(G)-splittable.Furthermore,if G is connected,then a'(G)>8(G),by