44 JOURNAL OF GRAPH THEORY Proof.(A)Suppose not.If g>3,then D=Kg.By (4).D.+y is contained in a brick B of H'-y.Then Bl>q.So q=5 and B=F1.Then @(F1)=4<5=0(D),a contradiction. Otherwise,g=3 and D.=Fs.See Figure 3B.The only vertex with degree 2 in D+y is y.It follows that y is incident to a cut-edge separating y from y.Thus it is possible to 3-color H'so that y and y have different colors,contradicting (5). (B)By (A)D.=K3.So D.+y=K4-e is contained in Dy(y')by (4).Thus by Proposition6.D,(-Fs. (C)Since yB.bo other neighbors of zare in B.One is u:let t be the neighbor not in Dy.See Figure 3C.Since uv,zyE(B).both z and u have degree two in B.Thus either B=K3 or B=Fs,depending on whether tuEE. (D)Since uv,zy &E(B),we have |E(Dy(y)+B.H'-(Dy(y)+B)<1.Thus,using (5). Y∈Dwoy)+B.Since yD,y.y'∈VB-D,). (E)Consider o∈Y-y.Eithero∈V(D)ori）o∈B.If(i)then v,since 间）then,again using5.例here品 tics for Theorem 29.Let Hbe a subgr aph ofG on qs+1 vertice Then H has at most four bad vertices and everyV(H)has at most wo d neighbors. Proof.Let veY.By(5).Y is monochromatic.Thus if x has three neighbors in Y then r has no me color class besides its own.Sincex is mo vable,H'-y opn ce (D)<2.By (5).Y is an independent set.Thus Y\V(D+y)0,and so the hypothesis of Proposition 28 holds.So4.by Proposition 28(E) ■ 6.CASEr=4 In this section we assume that b22 and show that a23 for all r.In particular this shows that Conjecture 3 holds for all graphs with maximum degree at most four. possibly non-optimal)nea equitable r- ring ofG satisfies a24 has a vertex v with dg(v)zb+2.In particular,v is movable. Proof. Suppose thatd)≤b+l for every vV-.Set G':=G[BUV-].Since every vertex in B has a neighbor in each class in A-V-,we have △(G)≤b+1<a+b=r sincea2.We will obtain a contradiction by showing that Ghas an equitable(b+1 coloring,and hence G has an equitable r-coloring.Suppose G does not have an equitable (b+1)-coloring.By Corollary 25,b+1 is odd,G'contains :=K+ and every (b+1)-coloring of G-O is equitable. Let O have bipartition (X.Y).Since by Proposition 17.A(G[B))<b.we may assume that Xnv-0.Then since V-is independent.YCB.Now again since A(G[B))sb. Journal of Graph Theory DOI 10
14 JOURNAL OF GRAPH THEORY Proof. (A) Suppose not. If q>3, then D y =Kq. By (4), D y+y is contained in a brick B of H −y . Then |B|>q. So q=5 and B=F1. Then (F1)=4<5=(D y), a contradiction. Otherwise, q=3 and D y=F5. See Figure 3B. The only vertex with degree 2 in D y+y is y. It follows that y is incident to a cut-edge separating y from y. Thus it is possible to 3-color H so that y and y have different colors, contradicting (5). (B) By (A) D y =K3. So D y+y=K4−e is contained in Dy(y ) by (4). Thus by Proposition 26, Dy(y )=F5. (C) Since y∈/ B, both other neighbors of z are in B. One is u; let t be the neighbor not in Dy. See Figure 3C. Since uv,zy∈/ E(B), both z and u have degree two in B. Thus either B=K3 or B=F5, depending on whether tu∈E. (D) Since uv,zy∈/ E(B), we have |E(Dy(y )+B,H −(Dy(y )+B)|≤1. Thus, using (5), y ∈Dy(y )+B. Since y ∈/ Dy(y ), y ∈V(B−Dy(y )). (E) Consider y0 ∈Y −y. Either (i) y0 ∈V(D y) or (ii) y0 ∈B. If (ii) then y0 =v, since y0 ∈/ N(y) by (5). If (iii) then, again using (5), there are at most two possibilities for y0, since (B−Dy)≤2. Theorem 29. Let H be a subgraph of G on qs+1 vertices with (H)≤q and (H)≤q. Then H has at most four bad vertices and every x∈V(H) has at most two bad neighbors. Proof. Let y∈Y. By (5), Y is monochromatic. Thus if x has three neighbors in Y, then x has no neighbors in some color class besides its own. Since x is movable, H −y is not q-equitable, a contradiction. Now suppose Y ≥4. By Proposition 27, D y is a complete graph or F5. In either case, (D y)≤2. By (5), Y is an independent set. Thus Y \V(D y+y)= ∅, and so the hypothesis of Proposition 28 holds. So |Y|≤4, by Proposition 28(E). 6. CASE r =4 In this section we assume that b≥2 and show that a≥3 for all r. In particular this shows that Conjecture 3 holds for all graphs with maximum degree at most four. Proposition 30. If a (possibly non-optimal) nearly equitable r-coloring of G satisfies a≥2, then its small class V− has a vertex v with dB(v)≥b+2. In particular, v is movable. Proof. Suppose that dB(v)≤b+1 for every v∈V−. Set G :=G[B∪V−]. Since every vertex in B has a neighbor in each class in A−V−, we have (G )≤b+1<a+b=r since a≥2. We will obtain a contradiction by showing that G has an equitable (b+1)- coloring, and hence G has an equitable r-coloring. Suppose G does not have an equitable (b+1)-coloring. By Corollary 25, b+1 is odd, G contains Q:=Kb+1,b+1, and every (b+1)-coloring of G −Q is equitable. Let Q have bipartition (X,Y). Since by Proposition 17, (G[B])≤b, we may assume that X∩V− = ∅. Then since V− is independent, Y ⊆B. Now again since (G[B])≤b, Journal of Graph Theory DOI 10.1002/jgt 44 JOURNAL OF GRAPH THEORY
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 45 XCV-.So V-\X is a color class of a (b+1)-coloring of G'-Q.Since (b+1)IV\XⅪ=(b+1)s-1-b-1)<(b+1)s-2)=1G-Q1 this coloring is not equitable,a contradiction Our next goal is to show that a>2.For a contradiction suppose a=2. Proposition 31.If zeV2 has a solo neighbor yeYeB,then z is not movable. Proof.Otherwise moving z to Vi yields a new nearly equitable coloring f with small class V2-z.Then z witnesses that Vi+zA(f)and y witnesses that YeA() Thus a≥3. Proposition 32. IfyeB is a good solo neighbor ofzeV2,then y is adjacent to every solo neighbor ofz Proo Bpo is not adjacent toyeBy definition V,has a movable 13 I,z nas a n y Is go B-y has an equita add z to one of th new color classes of B-y.This case yields a new nearly equitable coloring in which V2-z+y and the new class of y are both accessible.Thus a>3.Otherwise,z has exactly one neighbor in each class of B-y.Moving z to the class of y,y'to V2-z+y, and u from V2-z+y+y to Vi yields an equitable r-coloring. Proposition 33.If zeV2 is solo,then S:contains at most two bad vertices. Proof.Let u be a movable vertex in V2.Suppose z has three bad solo neighbors Then,as in Section 5.H:=G[B]contains some -Kb the graphH -0 is b-quasi-equitable,and every bad vertex is contained in the large color class X-O of H',where XEB.Since the solo vertex z is not movable and there exist at least three neighbors of z in X,there exists a class WeB with no neighbors of z.Move z to W and move two bad vertices yi.y2eSnX to V2 and u to Vi.This yields an equitable 2-coloring of G[A-+1+y2 nd a nearly equitable coloring of H":=H'+- These color an b equitabler-coloring contradiction ◆ Corollary34.For every z∈V2,lS,l≤b, Proof.Suppose S+1.By Proposition 33.S:contains at most two bad vertices. By Proposition 32 every good vertex in S:is adjacent to every other vertex in S2.Thus GS,+习contains K,-e.Sincer=a+b≥4，this contradicts Proposition8. ■ A vertex zV2 is f-special if it has at least b+1 neighbors in B,at least b of them are solo neighbors,and at least b-1 of the solo neighbors are good. Proposition 35.IfV is f-special,then it has a unique neighbor weV and w has at least two neighbors in V2.Moreover.S.+z is an (r-1)-clique and w has no neighbors in S.. Proof.Since zis f-special,it has at least b solo neighbors in S,and at least b-1of them are good.By Proposition 32,each good vertex is adjacent to every vertex in S2. Journal of Graph Theory DOI 10.1002/jgt
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 15 X⊆V−. So V− \X is a color class of a (b+1)-coloring of G −Q. Since (b+1)|V− \X|=(b+1)(s−1−b−1)<(b+1)(s−2)=|G −Q|, this coloring is not equitable, a contradiction. Our next goal is to show that a>2. For a contradiction suppose a=2. Proposition 31. If z∈V2 has a solo neighbor y∈Y ∈B, then z is not movable. Proof. Otherwise moving z to V1 yields a new nearly equitable coloring f with small class V2−z. Then z witnesses that V1+z∈A(f ) and y witnesses that Y ∈A(f ). Thus a≥3. Proposition 32. If y∈B is a good solo neighbor of z∈V2, then y is adjacent to every solo neighbor of z. Proof. Suppose y is not adjacent to y ∈Sz−y. By definition, V2 has a movable vertex u. By Proposition 31, z has a neighbor in V1 and u=z. Move z out and y to V2. Since y is good, B−y has an equitable coloring. If possible, add z to one of the new color classes of B−y. This case yields a new nearly equitable coloring in which V2−z+y and the new class of y are both accessible. Thus a≥3. Otherwise, z has exactly one neighbor in each class of B−y. Moving z to the class of y , y to V2−z+y, and u from V2−z+y+y to V1 yields an equitable r-coloring. Proposition 33. If z∈V2 is solo, then Sz contains at most two bad vertices. Proof. Let u be a movable vertex in V2. Suppose z has three bad solo neighbors. Then, as in Section 5, H :=G[B] contains some Q=Kb,b, the graph H :=H−Q is b-quasi-equitable, and every bad vertex is contained in the large color class X−Q of H , where X∈B. Since the solo vertex z is not movable and there exist at least three neighbors of z in X, there exists a class W ∈B with no neighbors of z. Move z to W and move two bad vertices y1, y2 ∈Sz∩X to V2 and u to V1. This yields an equitable 2-coloring of G[A−z+y1+y2] and a nearly equitable coloring of H :=H +z−y1−y2. These colorings can be combined with a nearly equitable coloring of Q to obtain an equitable r-coloring of G, a contradiction. Corollary 34. For every z∈V2, |Sz|≤b. Proof. Suppose |Sz|≥b+1. By Proposition 33, Sz contains at most two bad vertices. By Proposition 32 every good vertex in Sz is adjacent to every other vertex in Sz. Thus G[Sz+z] contains Kr−e. Since r=a+b≥4, this contradicts Proposition 8. A vertex z∈V2 is f-special if it has at least b+1 neighbors in B, at least b of them are solo neighbors, and at least b−1 of the solo neighbors are good. Proposition 35. If z∈V2 is f-special, then it has a unique neighbor w∈V1 and w has at least two neighbors in V2. Moreover, Sz+z is an (r−1)-clique and w has no neighbors in Sz. Proof. Since z is f-special, it has at least b solo neighbors in Sz, and at least b−1 of them are good. By Proposition 32, each good vertex is adjacent to every vertex in Sz. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 45
46 JOURNAL OF GRAPH THEORY By Corollary neighbor of z in V1.By Proposition 12,w has no neighbors in S.,since otherwise G[S:+z+w]contains K,-E(K1.r-3).Suppose w has no other neighbors in A.Then switching z and w results in another nearly equitable coloring f'with a(f)>3,since each vertex of S2 is movable to V2-+w,a contradiction to the optimality of f. Proposition36.Ifb≥2，then a≥3. Proof.Suppose that b>2 and a=2.Let uEV2 be movable.Let f be the optimal coloring obtained from the original coloring f by moving u to Vi.Then f'has color classes V:=V2-u,V3:=Vi+u,V:=V3.....V:=V,.For z V2 (respectively,zv3). let a(z)(respectively,'()be the number of good solo neighbors of z with respect tof(respectively.f).Let B denote the number of bad ver ces in G[B].Forz∈Alet Pa)de ote the numbe of bad ve S:.By The rem29,B<4 b+2 in eover B. onjecture 3 is true for r p:= -0 and p: otherwise.Note that b-2p>0,since B=0 when b=2.By Proposition 33,B(z)<2 for all zA.We now do the following discharging: (RO)Assign a total charge of 2B]-2p to the vertices of B so that each vertex y receives charge 2 if it is good and charge 2(1-1/B)if it is bad. (R1 Each tes half of its charge ev enly to its neighbors in V2 and half of its ch y to its eighbors ir V2- Not e that v and so receives charge twice. Let c chi()denote the charge of x at the end of (R1). (R2)Each f-special vertex zEV2 forwards charge to its unique neighbor in Vi and each f-sp pecial vertex in forwardscharge to its unique neighbor in Let ch) th final charge of s of B send a charge of 2B-2p to the vertices of A.Since is movable in both colorings,it has no solo neighbors.Thus in the first redistribution (R1)it receives a charge of at most from each of its neighbors twice.So altogether it receives at most r=b+2.Since u is movable,it has no neighbors in A,and so gains no charge in the second redistribution (R2).Thus after(R2)the set A-u has total charge at least 2+2bs-20-(b+2)=2b(s-1)+b-20>2b(s-1)=blA-l So there exists a vertex wEA-u with charge ch(w)>b.Our goal is to show that this 之一oea的xn网Hae ion (R1)each vertex z∈ -u rec eives 1 charge from eac good solo in B.So we have ch(dn(2)+:D-B2) B(dn(2)+I:)) (6) 4 fS:=0,then by(6.ch1(a)≤ds(a)≤5≤b.Otherwise,by Proposition3l,dB(a)≤ b+1,and by Corollary 34,ISI<b.Thus for any zA-u.chi()<b+.Moreover,if chi(2)>b,then by (6),(dB()+S)-B()/4>b.By the above,this is possible only if dg(2)=b+1.IS:l b,and B()1.which yields (-1.Thus z is special. Journal of Graph Theory DOI 10.1002/jgt
16 JOURNAL OF GRAPH THEORY By Corollary 34, |Sz|≤b. Thus Sz+z is an (r−1)-clique. Since z is solo, it has a neighbor w∈V1 by Proposition 31. Since it has r−1 neighbors in B, w is a unique neighbor of z in V1. By Proposition 12, w has no neighbors in Sz, since otherwise G[Sz+z+w] contains Kr−E(K1,r−3). Suppose w has no other neighbors in A. Then switching z and w results in another nearly equitable coloring f with a(f )≥3, since each vertex of Sz is movable to V2−z+w, a contradiction to the optimality of f . Proposition 36. If b≥2, then a≥3. Proof. Suppose that b≥2 and a=2. Let u∈V2 be movable. Let f be the optimal coloring obtained from the original coloring f by moving u to V1. Then f has color classes V 1 :=V2−u,V 2 :=V1+u,V 3 :=V3,...,V r :=Vr. For z∈V2 (respectively, z∈V 2), let (z) (respectively, (z)) be the number of good solo neighbors of z with respect to f (respectively, f ). Let denote the number of bad vertices in G[B]. For z∈A let (z) denote the number of bad vertices in Sz. By Theorem 29, ≤4; moreover =0 if r=b+2=4, since Conjecture 3 is true for r=2. Define :=1 if >0 and :=0 otherwise. Note that b−2>0, since =0 when b=2. By Proposition 33, (z)≤2 for all z∈A. We now do the following discharging: (R0) Assign a total charge of 2|B|−2 to the vertices of B so that each vertex y receives charge 2 if it is good and charge 2(1−1/) if it is bad. (R1) Each y∈B distributes half of its charge evenly to its neighbors in V2 and half of its charge evenly to its neighbors in V 2. Note that u∈V2∩V 2, and so receives charge twice. Let ch1(x) denote the charge of x at the end of (R1). (R2) Each f-special vertex z∈V2 forwards 1 2 charge to its unique neighbor in V1 and each f -special vertex in V 2 forwards 1 2 charge to its unique neighbor in V 1. Let ch(x) denote the final charge of x. Altogether the vertices of B send a charge of 2|B|−2 to the vertices of A. Since u is movable in both colorings, it has no solo neighbors. Thus in the first redistribution (R1) it receives a charge of at most 1 2 from each of its neighbors twice. So altogether it receives at most r=b+2. Since u is movable, it has no neighbors in A, and so gains no charge in the second redistribution (R2). Thus after (R2) the set A−u has total charge at least 2+2bs−2−(b+2)=2b(s−1)+b−2>2b(s−1)=b|A−u|. So there exists a vertex w∈A−u with charge ch(w)>b. Our goal is to show that this is a contradiction. In redistribution (R1) each vertex z∈A−u receives 1 charge from each good solo neighbor, (1− 1 ) from each bad solo neighbor and at most 1 2 from every other neighbor in B. So we have ch1(z)≤ 1 2 (dB(z)+|Sz|)− (z) ≤ 1 2 (dB(z)+|Sz|)− (z) 4 . (6) If Sz = ∅, then by (6), ch1(z)≤ 1 2 dB(z)≤ r 2 ≤b. Otherwise, by Proposition 31, dB(z)≤ b+1, and by Corollary 34, |Sz|≤b. Thus for any z∈A−u, ch1(z)≤b+ 1 2 . Moreover, if ch1(z)>b, then by (6), 1 2 (dB(z)+|Sz|)−(z)/4>b. By the above, this is possible only if dB(z)=b+1, |Sz|=b, and (z)≤1, which yields (z)≥b−1. Thus z is special. Journal of Graph Theory DOI 10.1002/jgt 46 JOURNAL OF GRAPH THEORY
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 47 Now consider the situation after round(R2).Each vertex z with charge chi()>b,is special,and so loses charge to its unique (non-special)neighbor in A.Thus ch(z)sb. So,if ch(w)>b,then w gained charge in redistribution(R2).Thus w is the unique neighbor (in a)of at least one special vertex.by symmetry.we may assume that we vr Using Prop position 35.da(w)>2.In total w gains at most 1 from each neighbor in B and at most from each neighbor in A.Thus da(w)<3 and so one of the following cases holds Case 1.w has exactly one f-special neighbor zEV2.By Proposition 35.w has another neighbor,say z,in V2.In our case,w does not receive any charge from 2. Thus,to have ch(w)>b,we need Swl=b and B(w)<1 (and so a'(w)>b-1).By Proposition 32 applied to wV2,ev ighbor of w is adja othe ne or of G(w)≥ -1,Sw+w is an (r 211 clique Choo good y∈S .By Proposition 12.since z is adjacent to w.is not adjacent to y.Move w out of Vi and move both z and y into Vi.Next,using that y is good,equitably color B-y with b colors.Since z'.y,EN(w),dg-y(w)<b-1.So we can move w into a class of B-y.This yields a nearly equitable coloring of G.This coloring has at least three accessible color classes,since z and each vertex in S.are now movable to the small class V2-z.This contradicts the optimality of f. Case 2.w has exactly two f-special neighbors 1,2EV2.To have ch(w)>b.w has to receive charge greater than b-1 from the remaining b neighbors.So we need dB(w)=b and Swl>b-1.Switch w with both zI and z2.This yields a nearly equitable coloring with small class V2-z1-z2+w.By Proposition 35,w has no neighbors in S It follows that each vertex in S.is movable to V2-z1-2+w.By Proposition 30. V-w has a vertex that is movable to V2:note that it is also movable to V2+w.So. as in Case 1,the new coloring has at least three accessible color classes Case 3.w has exactly three f-special neighbors 1.2.23EV2.They give w the charge 3.In order to receive charge greater than b-from the remaining b-1 neighbors,w needs Swl=b-1 and a'(w)>1.Move w out and z and z2 to Vi.Move a good yeS,to V2-z1-z2.Since y is good.B-y has an equitable b-coloring g. Since da(w)r-3=b-1.we can add w to one of the classes of g to obtain a nearly r-colorin of G w mall class V+:=V2 -+y.By the definition y(G).Since (B)=b anc Sa is a b que,we ca ch ose y e5. so that yyE.So again,the new coloring has at least three accessible color classe since both z2 and y'are movable to V. Lemma 23 and Proposition 36 yield our main result: Theorem 37. Conjecture 3 is true for r<4. ACKNOWLEDGMENTS The authors thank the referees for taking great care in reading our text and making useful suggestions. Journal of Graph Theory DOI 10.1002/jgt
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 17 Now consider the situation after round (R2). Each vertex z with charge ch1(z)>b, is special, and so loses 1 2 charge to its unique (non-special) neighbor in A. Thus ch(z)≤b. So, if ch(w)>b, then w gained charge in redistribution (R2). Thus w is the unique neighbor (in A) of at least one special vertex. By symmetry, we may assume that w∈V1. Using Proposition 35, dA(w)≥2. In total w gains at most 1 from each neighbor in B and at most 1 2 from each neighbor in A. Thus dA(w)≤3 and so one of the following cases holds. Case 1. w has exactly one f-special neighbor z∈V2. By Proposition 35, w has another neighbor, say z , in V2. In our case, w does not receive any charge from z . Thus, to have ch(w)>b, we need |Sw|=b and (w)≤1 (and so (w)≥b−1). By Proposition 32 applied to w∈V 2, every good solo neighbor of w is adjacent to every other solo neighbor of w. Since (w)≥b−1, Sw+w is an (r−1)-clique. Choose a good y∈Sw. By Proposition 12, since z is adjacent to w, z is not adjacent to y. Move w out of V1 and move both z and y into V1. Next, using that y is good, equitably color B−y with b colors. Since z , y,z∈N(w), dB−y(w)≤b−1. So we can move w into a class of B−y. This yields a nearly equitable coloring of G. This coloring has at least three accessible color classes, since z and each vertex in Sz are now movable to the small class V2−z. This contradicts the optimality of f . Case 2. w has exactly two f-special neighbors z1,z2 ∈V2. To have ch(w)>b, w has to receive charge greater than b−1 from the remaining b neighbors. So we need dB(w)=b and |Sw|≥b−1. Switch w with both z1 and z2. This yields a nearly equitable coloring with small class V2−z1−z2+w. By Proposition 35, w has no neighbors in Sz. It follows that each vertex in Sz1 is movable to V2−z1−z2+w. By Proposition 30, V1−w has a vertex that is movable to V2; note that it is also movable to V2+w. So, as in Case 1, the new coloring has at least three accessible color classes. Case 3. w has exactly three f-special neighbors z1,z2,z3 ∈V2. They give w the charge 3 2 . In order to receive charge greater than b− 3 2 from the remaining b−1 neighbors, w needs |Sw|=b−1 and (w)≥1. Move w out and z1 and z2 to V1. Move a good y∈Sz1 to V2−z1−z2. Since y is good, B−y has an equitable b-coloring g. Since dB(w)≤r−3=b−1, we can add w to one of the classes of g to obtain a nearly equitable r-coloring of G with small class V∗ 1 :=V2−z1−z2+y. By the definition of solo vertices, yz2 ∈/ E(G). Since (B)=b and Sz2 is a b-clique, we can choose y ∈Sz2 so that yy ∈/ E. So again, the new coloring has at least three accessible color classes, since both z2 and y are movable to V∗ 1 . Lemma 23 and Proposition 36 yield our main result: Theorem 37. Conjecture 3 is true for r≤4. ACKNOWLEDGMENTS The authors thank the referees for taking great care in reading our text and making useful suggestions. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 47
48 JOURNAL OF GRAPH THEORY REFERENCES [1]J.Blazewicz,K.Ecker,E.Pesch,G.Schmidt,and J.Weglarz,Scheduling Computer and Manufacturing Processes(2nd edn.),Springer,Berlin,2001, P. 85 [2]B.-L.Chen,K.-W.Lih,and P.-L.Wu,Equitable coloring and the maximum degree,Eur J Combin 15 (1994).443-447. [3]A.Hajnal and E.Szemeredi,Proof of a conjecture of P.Erdos,In: Combinatorial Theory and its Application(P.Erdos,A.Renyi,and V.T.Sos, Eds.),North-Holland,London,1970.pp.601-623. [4]H.A.Kierstead and A.V.Kostochka,A short proof of the Hajnal-Szemeredi Theorem on equitable coloring,Combin Probab Comput 17 (2008), 265-270 [5]H.A.Kierstead and A.V.Kostochka,An Ore- typ e theorem on equitable coloring,J Combin Theory Ser B 98(2008).226-234. [6]H.A.Kierstead and A.V.Kostochka,Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture.Combinatorica 30 (2010). 201-216 [7]H.A.Kierstead,A.V.Kostochka,M.Mydlarz,and E.Szemeredi,A fast algorithm for equitable coloring,Combinatorica 30(2010),217-224. [8]H.A.Kierstead,A.V.Kostochka,and G.Yu,Extremal graph packing problems:ore-type versus Dirac-type,In:Surveys in Combinatorics 2009, Mathematical Society Lecture Note Series 365(S.Huczynska,J.Mitchell, and C. Roney-Dougal,Eds.),Cambridge University Press,Cambridge,2009, pp.113-136. 19 A.V.Kostochka and K.Nakprasit,On equitable A-coloring of graphs with low average degree,Theor Comp Sci(2005).8-91. [10]K.-W.Lih and P.-L.Wu,On equitable coloring of bipartite graphs,Discrete Math151(1996.155-160. [11]B.F.Smith,P.E.Bjorstad,and W.D.Gropp,Domain Decomposition Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press,Cambridge,1996,pp.224. [12]A.Tucke r.Perfect graphs and a n application to optimizing municipal services,SIAM Rev 15(1973),585-590. [13]H.-P.Yap and Y.Zhang,The equitable A-colouring conjecture holds for rplanar graphs,Bull Inst Math Acad Sin 5(197),143-149. [14]H.-P.Yap andY.Zhang.Equitable colourings of planar graphs.JComb Math Comb Comp27(1998).97-105. Journal of Graph Theory DOI 10
18 JOURNAL OF GRAPH THEORY REFERENCES [1] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Scheduling Computer and Manufacturing Processes (2nd edn.), Springer, Berlin, 2001, p. 485. [2] B.-L. Chen, K.-W. Lih, and P.-L. Wu, Equitable coloring and the maximum degree, Eur J Combin 15 (1994), 443–447. [3] A. Hajnal and E. Szemeredi, Proof of a conjecture of P. Erd˝ ´ os, In: Combinatorial Theory and its Application (P. Erd˝os, A. Renyi, and V. T. S ´ os, ´ Eds.), North-Holland, London, 1970, pp. 601–623. [4] H. A. Kierstead and A. V. Kostochka, A short proof of the Hajnal–Szemeredi ´ Theorem on equitable coloring, Combin Probab Comput 17 (2008), 265–270. [5] H. A. Kierstead and A. V. Kostochka, An Ore-type theorem on equitable coloring, J Combin Theory Ser B 98 (2008), 226–234. [6] H. A. Kierstead and A. V. Kostochka, Equitable versus nearly equitable coloring and the Chen–Lih–Wu Conjecture, Combinatorica 30 (2010), 201–216. [7] H. A. Kierstead, A. V. Kostochka, M. Mydlarz, and E. Szemeredi, A fast ´ algorithm for equitable coloring, Combinatorica 30 (2010), 217–224. [8] H. A. Kierstead, A. V. Kostochka, and G. Yu, Extremal graph packing problems: ore-type versus Dirac-type, In: Surveys in Combinatorics 2009, Mathematical Society Lecture Note Series 365 (S. Huczynska, J. Mitchell, and C. Roney-Dougal, Eds.), Cambridge University Press, Cambridge, 2009, pp. 113–136. [9] A.V. Kostochka and K. Nakprasit, On equitable -coloring of graphs with low average degree, Theor Comp Sci 349 (2005), 82–91. [10] K.-W. Lih and P.-L. Wu, On equitable coloring of bipartite graphs, Discrete Math 151 (1996), 155–160. [11] B. F. Smith, P. E. Bjorstad, and W. D. Gropp, Domain Decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, Cambridge, 1996, pp. 224. [12] A. Tucker, Perfect graphs and an application to optimizing municipal services, SIAM Rev 15 (1973), 585–590. [13] H.-P. Yap and Y. Zhang, The equitable -colouring conjecture holds for outerplanar graphs, Bull Inst Math Acad Sin 5 (1997), 143–149. [14] H.-P. Yap and Y. Zhang, Equitable colourings of planar graphs, J Comb Math Comb Comp 27 (1998), 97–105. Journal of Graph Theory DOI 10.1002/jgt 48 JOURNAL OF GRAPH THEORY