EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 35 Now suppose y':=y is adjacent to every vertex of Y.So the vertices of Z are interchangeable with y.Since X+y is not an(r+1)-clique,Z+:=Z+y is not a (k+1)- clique.We claim that we can choose v.zZ+so that vzE and No(v)UNG() is not an r-clique:First.note that IN(v)l.IN()I<k.If r is odd,then IN( NG(<2k<r.Otherwis r ic ov nd so r 7+is independe 4.Suppo ose the claim is false.Then by degree considerations,2 t,and NG(w)nNG(2= for all w. Since r≥4，lZl=k+l≥3.So each v'eNc(W)satisfies d(w")≥3k,a contradiction Set G+:=G'+:EN(zI)).Then A(G+)<r and,by our claim,(G+)<r.If r is odd,then dG+(v)s2k<r,and so G+does not contain Kr.r.Thus by the minimality of G,there exists an equitable r-coloring f of G+.Since NG+()CNG+(v),f(v)EA(z). Using Remark 7 we can extend f to an equitable r-coloring of G:First,color with f(),then color the rest of Z.and finally color Y.all with distinct colors Proposition 9.If r=2k+1,then G does not contain K2k2k. Proof.Suppose that GlU]is a copy of K2k.2k with bipartition (Y1.Y2).Let G':= G-U.Each uU has at most one neighbor in G.Call it u'if it exists.If k=1,then by Proposition 6,for i=1,2 graph G[Yi]has no edges.Otherwise,A(G[Yil)s1<k. In both cases,G[Yil has an equitable k-coloring.So we can partition U into 2k-1 independent 2-sets B. I and two single tons (un ).(u hich ust be in the same part. m that we can pick the partit n so that≠(naybe be does not exist):If for somei]no vertex of Gis adjacent to every vertex of Y.this is easy:otherwise,G contains K.r-e,contradicting Proposition 6.Choose notation so that Bi=(vi,y).Define X:=(y1,....y2-1,u1,u2)and G:=G-X+42+by:ie2k-1}+{byy:1≤i<j≤2k-1, where edges involving u for uU do not exist if does not exist.Then dG+(y;)<r-1 for all ie[2k-1] (2) and do+A≤r for all ie2l.SoA(Gt)≤r.Suppc ose that Gf contains Ke.) Then by ().K does not c not contain y for any ie1]. Since yiyie also does K-u.contradicting Proposition 6.Thus ()r and G+does not contain Krr.By the minimality of G. G+has an r-coloring f.Extendf to an equitable coloring of G by first coloring each yi with the same color as y*and then coloring u and u2 with the remaining two colors which is possible,since f()f().This contradicts the choice of G. Proposition 10.If r=2k,then G does not contain Kkr-as an induced subgraph. Proof We first prove the tat ement that G does not contain Kr as an induced subgraph.Suppose G[YUY'UZ]=Kr with bipartition (YUY,Z).where Y= (y1,....yl.Y'=ty,...,y).and Z=(z1,...,z).Let :=ZUY and G:=G-X.Obtain G+from G'by adding all edges between y;and the neighbors of yi in G'for each i[k]. Then A(G+)<r,since each vertex in X has at most k neighbors in G-X.Suppose that K is an (r+1)-clique in G+.Then K contains at most on vertex from the independent Thu ntain -clique of G. ition 8.Hence Siee r is sven.and using the minimality of .eabe coloring f. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 5 Now suppose y :=y 1 is adjacent to every vertex of Y. So the vertices of Z are interchangeable with y . Since X+y is not an (r+1)-clique, Z+ :=Z+y is not a (k+1)- clique. We claim that we can choose v ,z1 ∈Z+ so that v z1 ∈/ E and NG(v )∪NG(z1) is not an r-clique: First, note that |NG(v )|,|NG(z1)|≤k. If r is odd, then |NG(v )∪ NG(z1)|≤2k<r. Otherwise, r is even and so r≥4. Suppose the claim is false. Then by degree considerations, Z+ is independent, and NG(w)∩NG(z)= ∅ for all w,z∈Z+. Since r≥4, |Z+|=k+1≥3. So each v∈NG(v ) satisfies d(v)≥3k, a contradiction. Set G+ :=G +{v z :z ∈N(z1)}. Then (G+)≤r and, by our claim, (G+)≤r. If r is odd, then dG+(v )≤2k<r, and so G+ does not contain Kr,r. Thus by the minimality of G, there exists an equitable r-coloring f of G+. Since NG+ (z1)⊆NG+(v ), f(v )∈A(z1). Using Remark 7 we can extend f to an equitable r-coloring of G: First, color z1 with f(v ), then color the rest of Z, and finally color Y, all with distinct colors. Proposition 9. If r=2k+1, then G does not contain K2k,2k. Proof. Suppose that G[U] is a copy of K2k,2k with bipartition {Y1,Y2}. Let G := G−U. Each u∈U has at most one neighbor in G . Call it u if it exists. If k=1, then by Proposition 6, for i=1, 2 graph G[Yi] has no edges. Otherwise, (G[Yi])≤1<k. In both cases, G[Yi] has an equitable k-coloring. So we can partition U into 2k−1 independent 2-sets B1,...,B2k−1 and two singletons {u1},{u2}, which must be in the same part. We claim that we can pick the partition so that u 1 =u 2 (maybe because u 2 does not exist): If for some i∈[2] no vertex of G is adjacent to every vertex of Yi, this is easy; otherwise, G contains Kr,r −e, contradicting Proposition 6. Choose notation so that Bi = {yi, y∗ i }. Define X:= {y1,..., y2k−1,u1,u2} and G+ :=G−X+u 1u 2+{y i y∗ i :i∈[2k−1]}+{y∗ i y∗ j : 1≤i<j≤2k−1}, where edges involving u for u∈U do not exist if u does not exist. Then dG+(y∗ i )≤r−1 for all i∈[2k−1] (2) and dG+(u i )≤r for all i∈[2]. So (G+)≤r. Suppose that G+ contains K∈ {Kr+1,Kr,r}. Then by (2), K does not contain any y∗ i . Since y∗ i y i ∈E(G+) for i∈[2k−1], K also does not contain y i for any i∈[2k−1]. It follows that G contains K−u 1u 2, contradicting Proposition 6. Thus (G+)≤r and G+ does not contain Kr,r. By the minimality of G, G+ has an r-coloring f . Extend f to an equitable coloring of G by first coloring each yi with the same color as y∗ i and then coloring u1 and u2 with the remaining two colors, which is possible, since f(u 1)=f(u 2). This contradicts the choice of G. Proposition 10. If r=2k, then G does not contain Kk,r−1 as an induced subgraph. Proof. We first prove the weaker statement that G does not contain Kk,r as an induced subgraph. Suppose G[Y ∪Y ∪Z]=Kk,r with bipartition {Y ∪Y ,Z}, where Y = {y1,..., yk}, Y = {y 1,..., y k}, and Z = {z1,...,zk}. Let X:=Z∪Y and G :=G−X. Obtain G+ from G by adding all edges between y i and the neighbors of yi in G for each i∈[k]. Then (G+)≤r, since each vertex in X has at most k neighbors in G−X. Suppose that K is an (r+1)-clique in G+. Then K contains at most one vertex from the independent set {y 1,..., y k}. Thus K contains an r-clique of G, contradicting Proposition 8. Hence (G+)≤r. Since r is even, and using the minimality of G, G+ has an equitable r￾coloring f . Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 35