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/jgt
4 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
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 rcoloring f . Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 35
36 JOURNAL OF GRAPH THEORY construction.Nc(v:)CNG+(v).and so f(y)EA(y;)for all iek.Thus UAx)≥I[r]f[Y]I+IS']I≥2k-Y'S']I≥k+lS'I≥S XES Now suppose that G[YUY"UZ]=K-1 with bipartition (YUY",Z).where Y and Z are defined as above and Y":=y.....).Let X:=ZUY and G':=G-X.Obtain GI from G by adding all edges between y and the neighbors of yi in G for each ie[k-1].Again A(G)<r and G does not contain K.Since G does not contain Kn,∩e ym()=0.Each vertex of Z has at most one neighbor in G1-Y".If G-" distinct vertic ith ie[2]. then let G2=G+otherwise Gm G2 contai s Kr+1,then GI contains K+1-e,where the missing edge is 2.In this case.G contains K Since r>4,this contradicts Proposition 6;thus (G,)<r.By the minimality of G.G has an equitable r-coloring f.For every zEZ.A()=[r]\f[Y"]-f(2).if z'is defined: otherwise A()=[r]\fIY]. It suffices to show that (1)holds.Suppose that (1)fails for some SX.Let S'= A≥A+S]I≥IVY"\S]-f≥k+IS1 (3) By the choice of S.(3)yields S+S'l.It follows that Z+yg.Recall that by the construction of G2,f(f().Hence,similar to (3).we have UAx)≥A(1)UA(2I+/S']I≥I[fY"\S]I≥k+1+S1=S This contradicts the definition of S. ◆ Corollary 11.If r=4,then G does not contain K2.3. Proof. bse G contains 2.By Proposition 10.G]does not induce Thus G contains K-e,contradicting Proposition Proposition 12.If rz4,then G does not contain K,-E(K1r-3). Proof.Suppose XCV(G)and x.y,zEX are such that X-x is an (r-1)-clique and xy,E.By the minimality of G.G':=G-X has an equitable r-coloring f. Then IA(w)l≥r-2 for ev ry vEX-x.A(y).A(z)zr-1.and A(x)=2.We are done by mark 7 unless A(l≤ _I for all vEX and A(y)=A(2).In this has a neighbor EV(G)and it is unique if vely,).By Proposition 8,(G)<r.Thus there exists veX-x with vy E. Case 1.v=z.Set G+:=G'+z'y.Then A(G+)<r.By Proposition 6.G+does not contain KE(K+Kr,since otherwise G contains K-z'y. Journal of Graph Theory DOI 10.1002/jg
6 JOURNAL OF GRAPH THEORY It suffices to show (1). Fix S= ∅ and set S = {y i : yi∈S}. Note that |A(x)|≥k for all x∈X. Thus we may assume |S|>k. So there exists z∈S∩Z. Then A(z)=[r]\f[Y ]. By construction, NG(yi)⊆NG+(y i ), and so f(y i )∈A(yi) for all i∈[k]. Thus x∈S A(x) ≥|[r]\f[Y ]|+|f[S ]|≥2k−|f[Y \S ]|≥k+|S |≥|S|. Now suppose that G[Y ∪Y∪Z]=Kk,r−1 with bipartition {Y ∪Y,Z}, where Y and Z are defined as above and Y := {y 1,..., y k−1}. Let X:=Z∪Y and G :=G−X. Obtain G1 from G by adding all edges between y i and the neighbors of yi in G for each i∈[k−1]. Again (G1)≤r and G1 does not contain Kr+1. Since G does not contain Kk,r, z∈Z NG −Y(z)= ∅. Each vertex of Z has at most one neighbor in G1−Y. If NG −Y(Z) contains two distinct vertices, say z 1,z 2 with ziz i ∈E for i∈[2], then let G2 =G1+z 1z 2; otherwise G2 :=G1. Then (G2)≤r. If G2 contains Kr+1, then G1 contains Kr+1−e, where the missing edge is z 1z 2. In this case, G contains Kr−e. Since r≥4, this contradicts Proposition 6; thus (G2)≤r. By the minimality of G, G2 has an equitable r-coloring f . For every z∈Z, A(z)=[r]\f[Y]−f(z ), if z is defined; otherwise A(z)=[r]\f[Y]. It suffices to show that (1) holds. Suppose that (1) fails for some S⊆X. Let S = {y i : yi ∈S and i∈[k−1]}. Since G[X]=Kk,k, |A(y)|≥k for all y∈S. Thus |S|≥k+1 and so S contains a vertex zj ∈Z. Moreover, f(y i )∈A(yi)\A(zj) for all i∈[k−1]. So x∈S A(x) ≥|A(zj)|+|f[S ]|≥|[r]\f[Y \S ]−f(z j)|≥k+|S |. (3) By the choice of S, (3) yields |S|≥k+1+|S |. It follows that S⊇Z+yk. Recall that by the construction of G2, f(z 1)=f(z 2). Hence, similar to (3), we have x∈S A(x) ≥|A(z1)∪A(z2)|+|f[S ]|≥|[r]\f[Y \S ]|≥k+1+|S |=|S|. This contradicts the definition of S. Corollary 11. If r=4, then G does not contain K2,3. Proof. Suppose G contains K2,3. By Proposition 10, G[Q] does not induce K2,3. Thus G contains K4−e, contradicting Proposition 8. Proposition 12. If r≥4, then G does not contain Kr−E(K1,r−3). Proof. Suppose X⊆V(G) and x, y,z∈X are such that X−x is an (r−1)-clique and xy, xz∈E. By the minimality of G, G :=G−X has an equitable r-coloring f . Then |A(v)|≥r−2 for every v∈X−x, A(y),A(z)≥r−1, and A(x)≥2. We are done by Remark 7, unless |A(v)|≤r−1 for all v∈X and A(y)=A(z). In this case, every v∈X−x has a neighbor v ∈V(G ) and it is unique if v∈ {y,z}. By Proposition 8, (G)<r. Thus there exists v∈X−x with vy ∈/ E. Case 1. v=z. Set G+ :=G +z y . Then (G+)≤r. By Proposition 6, G+ does not contain K∈ {Kr+1,Kr,r}, since otherwise G contains K−z y . Journal of Graph Theory DOI 10.1002/jgt 36 JOURNAL OF GRAPH THEORY
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 37 Case 2.yveE andy=z.Let G+:=G'+ly'u:(v)).Then A(G+)sr,since do(y)s -2.By Propositiondoes not contain Ksinceo erwise G contain K-y=Kr.Suppose G contains K=Kr.r.Then by degree considerations,G[K-y] is an induced Kr-1,contradicting Proposition 9 or 10. So in both cases G+induces neither K nor Kr.By the minimality of G.we can choose an equitable r-coloring f of G+.By construction.f(y)A(v)\A(y).Hence(1) is true. Proposition 13.G does not contain a maximal independent set of size s. Proof.Suppose X is a maximal independent set and X]=s.Let G=G-X.Since X is maximal,A(G)sr-1.Thus,if G'contains K,-1.-1 then it is induced.So by Propositions 9 and 10.G'does not contain K-1-1.By Proposition 8,(G)<(G)< r-1.Thus by the minimality of G.Ghas an equitable (r-1)-coloring.Adding X as a color class vields an equitab ble r-c coloring of G. 3.OPTIMAL COLORINGS Recall that G is an edge-minimal counter-example to the Chen-Lih-Wu conjecture with sr vertices.A nearly equitable coloring is a coloring such that every color class has the same size s except for one small class V-with size s-1 and one large class V+with size s+1.The following lemma (Theorem 2 in [9])is used to show that G has a nearly equitable -coloring Lemma 14 (Kostochka and Nakprasit [9)).Let H be a graph with (H).A(H)<r Let uEV(H)andf be c y r-color ng of G-u with color class es VI .Vr.Then there is an r-ee with classes W1.....W,such that Wil=IVil for all bu one i Proposition 15.G has a nearly equitable r-coloring Proof.Let xyEE.By the minimality of G.G-xy has an equitable r-coloring.Thus G-x has an r-coloring with one class of size s-1 and all other classes of size s. Since G does not have an equitable r-coloring.Lemma 14 implies that G has a nearly equitable r-coloring Let f be a nearly equitable coloring of G with color classes V-=Vi .V=V+ an uxili s The ve rtices of H are the color cla cted edge belongs to E(H)if som no neighbors in V".In this case we say that x witnesses the edge color class Vi of f accessible if Vi is reachable from Vi in the digraph H(G.f).By definition,Vi is accessible.Let A:=A(f)denote the family of accessible classes,B denote the family of inaccessible classes,A:=A,and B:=B=V-A.If VA. then switchins V,∈B.Let witnesses along a path from yields an IAl and b:= Then IAl and B =bs+1 Call a ne e coloring of G imal if a is as large as pos sible.Fix an optimal coloring f=(V-=V1,....V,=V+),where the accessible classes Vi....,Va are Journal of Graph Theory DOI 10.1002/jgt
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 7 Case 2. y v∈/ E and y =z . Let G+ :=G +{y u:u∈NV\X(v)}. Then (G+)≤r, since dG(y )≤r−2. By Proposition 8, G+ does not contain Kr+1, since otherwise G contains K−y =Kr. Suppose G+ contains K =Kr,r. Then by degree considerations, G[K−y ] is an induced Kr,r−1, contradicting Proposition 9 or 10. So in both cases G+ induces neither Kr+1 nor Kr,r. By the minimality of G, we can choose an equitable r-coloring f of G+. By construction, f(y )∈A(v)\A(y). Hence (1) is true. Proposition 13. G does not contain a maximal independent set of size s. Proof. Suppose X is a maximal independent set and |X|=s. Let G =G−X. Since X is maximal, (G )≤r−1. Thus, if G contains Kr−1,r−1 then it is induced. So by Propositions 9 and 10, G does not contain Kr−1,r−1. By Proposition 8, (G )≤(G)≤ r−1. Thus by the minimality of G, G has an equitable (r−1)-coloring. Adding X as a color class yields an equitable r-coloring of G. 3. OPTIMAL COLORINGS Recall that G is an edge-minimal counter-example to the Chen–Lih–Wu conjecture with sr vertices. A nearly equitable coloring is a coloring such that every color class has the same size s except for one small class V− with size s−1 and one large class V+ with size s+1. The following lemma (Theorem 2 in [9]) is used to show that G has a nearly equitable r-coloring. Lemma 14 (Kostochka and Nakprasit [9]). Let H be a graph with (H),(H)≤r. Let u∈V(H) and f be any r-coloring of G−u with color classes V1, ...,Vr. Then there is an r-coloring of G with color classes W1, ...,Wr such that |Wi|=|Vi| for all but one i. Proposition 15. G has a nearly equitable r-coloring. Proof. Let xy∈E. By the minimality of G, G−xy has an equitable r-coloring. Thus G−x has an r-coloring with one class of size s−1 and all other classes of size s. Since G does not have an equitable r-coloring, Lemma 14 implies that G has a nearly equitable r-coloring. Let f be a nearly equitable coloring of G with color classes V− =V1,...,Vr =V+. Construct an auxiliary digraph H:=H(G,f) as follows. The vertices of H are the color classes V1,...,Vr. A directed edge V V belongs to E(H) if some vertex x∈V has no neighbors in V. In this case we say that x witnesses the edge V V. Call a color class Vi of f accessible if V1 is reachable from Vi in the digraph H(G,f). By definition, V1 is accessible. Let A:=A(f) denote the family of accessible classes, B denote the family of inaccessible classes, A:=A, and B:=B=V −A. If Vr ∈A, then switching witnesses along a path from Vr to V1 yields an equitable r-coloring; so Vr ∈B. Let a:=|A| and b:=|B|=r−a. Then |A|=as−1 and |B|=bs+1. Call a nearly equitable r-coloring of G optimal if a is as large as possible. Fix an optimal coloring f =(V− =V1,...,Vr =V+), where the accessible classes V1,...,Va are Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 37
38 JOURNAL OF GRAPH THEORY ordered(by breadth-first search)so that Vi is reachable from each accessible Vi by a path in H[Vi,...,Vil.An accessible class Vi is terminal if Vi can be reached from every accessible class VEA-Vi by a path in H-Vi.For example,Va is terminal. Class Vi is terminal if and only if a=1.A vertex veVi is movable to a class ViV if it has no neighbors in Vi.It is movable if it is movable to some accessible class. The next two propositions illustrate the utility of these definitions.The structural equitable of GLAl.and to bo und the degree of G[B]. the previous article degree bound n G[B]allowed us to apply the minimality of G to obtain an equitable b-coloring of G[B-y]for any vertex yEB. In the current setting this is more subtle when b is odd,since G[B]may contain Kb. Both propositions follow immediately from the definitions. Proposition 16.Let u be a movable vertex in a terminal class V.Then G[A-V:+u has an equitable (a-1)-coloring. Proposition17.△(GB)≤b andyB.is a sol eighbor of y.andy is a solo neighbo of x.if yeE and has n bors in V A vertex is a solo vertex,if it has a solo neighbor.For xA,let Sx be the set of solo neighbors of x. Lemma 18. a≥2 Proof.Assume that a=1,i.e..A=V1.Consider the weight function w:E(A.B) defined by w(x):=1/d)for every yE(G)such that eA and yeB.By defi- nition s y)=1 for every yeB.He the total weight of all edges in E(A,B)is bs+1.and so there exists xEA such that w(xy)>b=r-1.Since d(x)sr,it follows that IS2r-1.If Sx is a clique,then G[S+x]=K.contradicting Proposition 8.Thus x has two nonadjacent solo neighbors y and y.Move y to Vi and move x out of Vi to obtain V.Set G':=G[B-y].Then (G)<r-1.A(G)<r-1 by Proposition 17.anddoes not contain by P 0p0 sitions 9 and 10.By the minimality of G.has an equitable (r-1)-coloring V. If V+x is independent for some i,then moving x to V:yields a nearly equitable r-coloring of G with VA.a contradiction to the maximality of a.Otherwise,x has equitable r-coloring of G,a contradiction to the choice of G. 4.IFr<4,THEN b≥2 In this section we show that if3≤r≤4，then b≥2.Since a≥2，this will give a new vetheorem 4.About half of our argument works also for all r> We start fro m a nev otion A b aph F with a gi bipartition is ial if every ertex of y has degree artite graph with a given sefeverycompo ofFisither very spcial,ora pah with a even number of vertices,or a single vertex in X. The core of a graph G is the maximum subgraph H with (H)22.It exists if IGI<IGIL Journal of Graph Theory DOI 10
8 JOURNAL OF GRAPH THEORY ordered (by breadth-first search) so that V1 is reachable from each accessible Vi by a path in H[V1,...,Vi]. An accessible class Vi is terminal if V1 can be reached from every accessible class Vj ∈A−Vi by a path in H−Vi. For example, Va is terminal. Class V1 is terminal if and only if a=1. A vertex v∈Vi is movable to a class Vj =Vi if it has no neighbors in Vj. It is movable if it is movable to some accessible class. The next two propositions illustrate the utility of these definitions. The structural properties of H[A] allow us to find equitable a-colorings of G[A], and to bound the degree of G[B]. In the previous articles this degree bound on G[B] allowed us to apply the minimality of G to obtain an equitable b-coloring of G[B−y] for any vertex y∈B. In the current setting this is more subtle when b is odd, since G[B] may contain Kb,b. Both propositions follow immediately from the definitions. Proposition 16. Let u be a movable vertex in a terminal class Vt. Then G[A−Vt+u] has an equitable (a−1)-coloring. Proposition 17. (G[B])≤b. For x∈Vj∈A and y∈B, x is a solo neighbor of y, and y is a solo neighbor of x, if xy∈E and y has no other neighbors in Vj. A vertex is a solo vertex, if it has a solo neighbor. For x∈A, let Sx be the set of solo neighbors of x. Lemma 18. a≥2. Proof. Assume that a=1, i.e., A=V1. Consider the weight function w:E(A,B)→ Q defined by w(xy):=1/dA(y) for every xy∈E(G) such that x∈A and y∈B. By defi- nition, x∈N(y)∩Aw(xy)=1 for every y∈B. Hence the total weight of all edges in E(A,B) is bs+1, and so there exists x∈A such that y∈N(x)w(xy)>b=r−1. Since d(x)≤r, it follows that |Sx|≥r−1. If Sx is a clique, then G[Sx+x]=Kr, contradicting Proposition 8. Thus x has two nonadjacent solo neighbors y and y . Move y to V1 and move x out of V1 to obtain V 1. Set G :=G[B−y]. Then (G )≤r−1, (G )≤r−1 by Proposition 17, and G does not contain Kr−1,r−1 by Propositions 9 and 10. By the minimality of G, G has an equitable (r−1)-coloring V 2,...,V r. Suppose y ∈V j . If V i +x is independent for some i, then moving x to V i yields a nearly equitable r-coloring of G with V j ∈A, a contradiction to the maximality of a. Otherwise, x has exactly one neighbor in each class of G . Move x to V j and y to V 1. This yields an equitable r-coloring of G, a contradiction to the choice of G. 4. IF r ≤4, THEN b≥2 In this section we show that if 3≤r≤4, then b≥2. Since a≥2, this will give a new proof of Theorem 4. About half of our argument works also for all r≥3. We start from a new notion. A bipartite graph F with a given bipartition (X,Y) is very special if every vertex of Y has degree 2. A bipartite graph F with a given bipartition (X,Y) is special if every component of F is either very special, or a path with an even number of vertices, or a single vertex in X. The core of a graph G is the maximum subgraph H with (H)≥2. It exists if |G|≤ G . Journal of Graph Theory DOI 10.1002/jgt 38 JOURNAL OF GRAPH THEORY