34 JOURNAL OF GRAPH THEORY First is divisible by r.Then all classes of fi have the same size for =1.2.Thus we can obtain an equitable r-coloring of C,if we can matchhe classes of fi to the classes of f2 so that there are no edges connecting a class and its mate.If IFl<r this is possible because K.r-e1-...-er-1 has a perfect matching by Hall's theorem. If yi is not divisible by r then each f has small and large classes (differing in size by 1).To obtain a g(by m cla st mat ch mall palsaudoastp s qissod st sl jo sasse ao s clas ■ Proposition 6.G contains neither K+-e nor Kr-e Proof.Assume first that Glol=Ky with x.yEO.Set o':=0-y and G': G-O'.If x has a neighbor v ir n it is unique.In this case otherwise,let=.Notice that A(G r.Sin neither K Krr are co ed in G+.So by the mi ality of G. f with f(v)f(y).We can extend f to an equitable r-coloring of G by coloring x with f(y)and using the other r-I colors on the remaining r-1 vertices of '-x,whose neighbors are all in 2. Now assume G[o]=Krr-e.Then G[o]has an equitable r-coloring and so OV. Also,lE(Q,V八Q≤2<3≤r,which contradicts Proposition5. The following observation will be used repeatedly. Remark 7.Let XCV with X]=r and let f be an equitable r-coloring of G':=G-X. For xEX,let A(x):=Af(x):=[r]\(f(v):vEV(G')andvxEE(G))be the set of available colors for x.If the family A:=(A(x):X)has a set of distinct representatives,then G has an equitable r-coloring.Thus by Hall's theorem,if for every SX (1) then f can be extended to an equitable r-coloring of G. Proposition 8.Set k:=r/2].Then G does not contain K,-E(Kk). Pr00. Suppose not:say ZXCV satisfy XI=r,Z=k and every vertex of Y:= X-Z is adjacent to every other vertex of X.Set G':=G-X and V:=V(G).Then dy(y)sI for all yeY and dy(z)<k for all zeZ.For each yeY,if y has a neighbor in G'then it is unique;in this case denote its neighbor by y. First,suppose that no vertex of G'is adjacent to every vertex of Y.Choose y.y2EY so that eithe has no neighbor in and set G+:=G'in the fo Case and G+: +以in the latter.Then A(G By Proposition6 neither Kr+1 nor Kr.r,since otherwise G would contain Kr+1-e or Krr-e.Thus by the minimality of G.there exists an equitable r-coloring f of G+(and of G)with fy)≠f6)if y exists.SolA(zl=r-k(≥k)for zEZ,Aoy川≥r-1 for yey,and A(yI)UA(y2)|=r.Suppose that (1)fails for an SCX.Since A(x)>k for every xEX. there existsy∈YnS.Since A≥r-l,S=X,and so IUresA()≥AG)UA2=7 a contradiction Journal of Graph Theory DOI 10.1002/jgt4 JOURNAL OF GRAPH THEORY First, suppose that |Y1| is divisible by r. Then all classes of fi have the same size for i=1, 2. Thus we can obtain an equitable r-coloring of G, if we can match the color classes of f1 to the classes of f2 so that there are no edges connecting a class and its mate. If |F|<r this is possible because Kr,r −e1−···−er−1 has a perfect matching by Hall’s theorem. If Y1 is not divisible by r, then each fi has small and large classes (differing in size by 1). To obtain an equitable r-coloring (by matching classes), we must match small classes of f1 to large classes of f2. This is possible if |F|=0, i.e., G is disconnected. Proposition 6. G contains neither Kr+1−e nor Kr,r −e. Proof. Assume first that G[Q]=Kr+1−xy with x, y∈Q. Set Q :=Q−y and G := G−Q . If x has a neighbor v in G , then it is unique. In this case set G+ :=G +vy; otherwise, let G+ :=G . Notice that (G+)≤r. Since degG+(y)≤2<r, neither Kr+1 nor Kr,r are contained in G+. So by the minimality of G, G+ has an equitable r-coloring f with f(v)=f(y). We can extend f to an equitable r-coloring of G by coloring x with f(y) and using the other r−1 colors on the remaining r−1 vertices of Q −x, whose neighbors are all in Q. Now assume G[Q]=Kr,r−e. Then G[Q] has an equitable r-coloring and so QV. Also, |E(Q,V \Q)|≤2<3≤r, which contradicts Proposition 5. The following observation will be used repeatedly. Remark 7. Let X⊆V with |X|=r and let f be an equitable r-coloring of G :=G−X. For x∈X, let A(x):=Af(x):=[r]\{f(v): v∈V(G ) andvx∈E(G)} be the set of available colors for x. If the family A:= {A(x): x∈X} has a set of distinct representatives, then G has an equitable r-coloring. Thus by Hall’s theorem, if |S|≤ x∈S A(x) for every S⊆X (1) then f can be extended to an equitable r-coloring of G. Proposition 8. Set k := r/ 2. Then G does not contain Kr−E(Kk). Proof. Suppose not; say Z ⊆X⊆V satisfy |X|=r, |Z|=k and every vertex of Y := X−Z is adjacent to every other vertex of X. Set G :=G−X and V :=V(G ). Then dV(y)≤1 for all y∈Y and dV(z)≤k for all z∈Z. For each y∈Y, if y has a neighbor in G then it is unique; in this case denote its neighbor by y . First, suppose that no vertex of G is adjacent to every vertex of Y. Choose y1, y2 ∈Y so that either y1 has no neighbor in G or y 1 =y 2, and set G+ :=G in the former case and G+ :=G +y 1y 2 in the latter. Then (G+)≤r. By Proposition 6, G+ contains neither Kr+1 nor Kr,r, since otherwise G would contain Kr+1−e or Kr,r −e. Thus by the minimality of G, there exists an equitable r-coloring f of G+ (and of G ) with f(y 1)=f(y 2) if y 1 exists. So |A(z)|=r−k (≥k) for z∈Z, |A(y)|≥r−1 for y∈Y, and |A(y1)∪A(y2)|=r. Suppose that (1) fails for an S⊆X. Since |A(x)|≥k for every x∈X, there exists y∈Y ∩S. Since |A(y)|≥r−1, S=X, and so | x∈S A(x)|≥|A(y1)∪A(y2)|=r, a contradiction. Journal of Graph Theory DOI 10.1002/jgt 34 JOURNAL OF GRAPH THEORY