(2008)17 265-270 2007 Cambridge University Pre nline 5 July 2007 Printed in the United Kingdom A Short Proof of the Hajnal-Szemeredi Theorem on Equitable Colouring H.A.KIERSTEAD!t and A.V.KOSTOCHKA2 Department of Mathematics and Statistics,Arizona State University.Tempe,AZ85287.USA (e-mail:kiersteadeasu.edu) Department of Mathematics,University of Illinois,Urbana.IL61801.USA and Institute of Mathematics,Novosibirsk.63009.Russia (e-mail:kostochk math.uiuc.edu) Received 7 August 2006:revised 28 March 2007 ger r ever graph with maximum degree at most r has an equitable colouring withr+ colours.The proof yields apolynomial time algorithm for such colourings. 1.Introduction An equitable k-colouring of a graph G is a proper k-colouring,for which any two colour classes differ in size by at most one.Equitable colourings naturally arise in some scheduling.partition ing,and load-balancing problems [1,15,16].Pemmaraju [13]and Janson and Rucinski [6]used equitable colourings to derive deviation bounds for sums of random variables that exhibit limited dependence.In 1964 Erdos [3]conjectured that any graph with maximum degree A(G)rhas an equitable (r+1)-colouring.This conjecture was proved in 1970 by Hainal and Szemeredi [5]with a surprisingly long and complicated argument.Recently,Mydlarz and Szemeredi [11] found a polynomial time algorithm for such colourings. In search of an easier proof,Seymour [14]strengthened Erdos's conjecture by asking whether every graph with)thekth power of a Hamilonian cycle. (If G]=(r +1)(s+1)and A(G)<r then (G)Gl:each (s +1)-interval of an sth powe of a Hamiltonian cycle in G is an independent set in G.)The case k 1 is Dirac's theorem and the casek=2 is Posa's conjecture.Fan and Kierstead [4]proved Posa's conjecture with'cycle' dNSDMS-4004n DMS-065074 and by grant 05-01 00816 of the Russian Foundation for Basic Research
Combinatorics, Probability and Computing (2008) 17, 265–270. c 2007 Cambridge University Press doi:10.1017/S0963548307008619 First published online 5 July 2007 Printed in the United Kingdom A Short Proof of the Hajnal–Szemeredi Theorem ´ on Equitable Colouring H. A. KIERSTEAD1† and A. V. KOSTOCHKA2‡ 1Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287, USA (e-mail: kierstead@asu.edu) 2Department of Mathematics, University of Illinois, Urbana, IL 61801, USA and Institute of Mathematics, Novosibirsk, 630090, Russia (e-mail: kostochk@math.uiuc.edu) Received 7 August 2006; revised 28 March 2007 A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemeredi theorem: for every positive ´ integer r, every graph with maximum degree at most r has an equitable colouring with r + 1 colours. The proof yields a polynomial time algorithm for such colourings. 1. Introduction An equitable k-colouring of a graph G is a proper k-colouring, for which any two colour classes differ in size by at most one. Equitable colourings naturally arise in some scheduling, partitioning, and load-balancing problems [1, 15, 16]. Pemmaraju [13] and Janson and Rucinski [6] used ´ equitable colourings to derive deviation bounds for sums of random variables that exhibit limited dependence. In 1964 Erdos [3] conjectured that any graph with maximum degree ˝ ∆(G) r has an equitable (r + 1)-colouring. This conjecture was proved in 1970 by Hajnal and Szemeredi ´ [5] with a surprisingly long and complicated argument. Recently, Mydlarz and Szemeredi [11] ´ found a polynomial time algorithm for such colourings. In search of an easier proof, Seymour [14] strengthened Erdos’s conjecture by asking whether ˝ every graph with minimum degree δ(G) k k+1 |G| contains the kth power of a Hamiltonian cycle. (If |G| = (r + 1)(s + 1) and ∆(G) r then δ(G) s s+1 |G|; each (s + 1)-interval of an sth power of a Hamiltonian cycle in G is an independent set in G.) The case k = 1 is Dirac’s theorem and the case k = 2 is Posa’s conjecture. Fan and Kierstead [4] proved P ´ osa’s conjecture with ‘cycle’ ´ † Research of this author is supported in part by NSA grant MDA 904-03-1-0007. ‡ Research of this author is supported in part by NSF grants DMS-0400498 and DMS-0650784, and by grant 05-01- 00816 of the Russian Foundation for Basic Research.
266 H.A.Kierstead and A.V.Kostochka replaced by 'path'.Komlos,Sarkozy and Szemeredi [7]proved Seymour's conjecture for graphs y ma any (in terms ofk)vertices.Neither of these partial results has a simple proof In fact,Komlos,Sarkozy and Szemeredi [7]use the Regularity Lemma,the Blow-up Lemma and the Hainal-Szemeredi theorem. A different strengthening was suggested recently by Kostochka and Yu [9,10].In the spiri of Ore's theorem on Hamiltonian cycles [12].they conjectured that every graph in which d(x)+ d(y)S 2r for every edge xy has an equitable (r+1)-colouring. In this paper we present a short proof of the Hajnal-Szemeredi theorem and present anothe polynomial time algorithm that constructs an equitable(r+1)-colouring of any graph G with maximum degree A(G)<r.Our approach is similar to the original method,but a discharging argument leads to a simpler conclusion.Our techniques have paid further dividends.In anothe paper we will prove the above conjecture of Kostochka and Yu [9,10]in a stronger form:with 2r+1 in place of 2r.They also yield partial results towards the Chen-Lih-Wu conjecture [2] about equitable r-colourings of r-regular graphs and towards a list analogue of Hajnal-Szemered theorem (see 8]for definitions). Most of our notation is standard:possible exceptions include the following.for a vertex v and set of vertices X.Nx(y):=N(y)and dx(y):=INx(y)l.If u is a function on the edge set.then u(A.B)=> vE(AB)u(x,y).where E(A,B)is the set of edges joining a vertex in A to a vertex in B.For a function f:V-Z,the restriction of f to WV is denoted by flw. Functions are viewed formally as sets of ordered pairs.Thus.g=f(u)is the extension of f to VUu such that g(u)=7. 2.Main result Let G be a graph with s(r+1)vertices satisfying A(G)<r.A nearly equitable (r+1)-colouring of G is a proper colouring f,whose colour classes all have size s except for one small class V-=V-(f)with size s-1 and one large class V+=V+(f)with size s+1.Given such a colouring f,define an auxiliary digraph H=H(G.f)as follows.The vertices of H are the colour classes of f,and a directed edge VW belongs to E(H)if and only if some vertex y V has no neighbours in W.In this case we say that y is movable to W.Call WEV(H)accessible if V-is reachable from Win H.Note that V-is trivially accessible.Letf denote the family of accessible classes,A :=U./and B:=V(G)\A.Let m :=-1 and g:=r-m. Then Al =(m+1)s-1 and |B]=(r-m)s+1.Lety E B.Since y cannot be moved to A. d4y)≥m+1 and hence da(y)≤q-L. (2.1) Lemma 2.1.If G has a nearly equitable(r+1)-colouring f whose large class V+is access ible,then G has an equitable(r+1)-colouring. Proof.Let :V1...Ve be a path in H(G,f)from V:=V+to V:=V-.This means that for eachj=1....-1.V contains a vertex y that has no neighbours in V+.So,if we move yi to Vj+i for j=1,...,k-1,then we obtain an equitable (r+1)-colouring of G. Suppose V+s B.If A V-then |E(A,B)rV-|=r(s-1)<1+rs |Bl.a contradic tion to (2.1).Thus m+1=2.Call a class VE terminal if V-is reachable from every
266 H. A. Kierstead and A. V. Kostochka replaced by ‘path’. Komlos, S ´ ark ´ ozy and Szemer ˝ edi [7] proved Seymour’s conjecture for graphs ´ with sufficiently many (in terms of k) vertices. Neither of these partial results has a simple proof. In fact, Komlos, S ´ ark ´ ozy and Szemer ˝ edi [7] use the Regularity Lemma, the Blow-up Lemma and ´ the Hajnal–Szemeredi theorem. ´ A different strengthening was suggested recently by Kostochka and Yu [9, 10]. In the spirit of Ore’s theorem on Hamiltonian cycles [12], they conjectured that every graph in which d(x) + d(y) 2r for every edge xy has an equitable (r + 1)-colouring. In this paper we present a short proof of the Hajnal–Szemeredi theorem and present another ´ polynomial time algorithm that constructs an equitable (r + 1)-colouring of any graph G with maximum degree ∆(G) r. Our approach is similar to the original method, but a discharging argument leads to a simpler conclusion. Our techniques have paid further dividends. In another paper we will prove the above conjecture of Kostochka and Yu [9, 10] in a stronger form: with 2r + 1 in place of 2r. They also yield partial results towards the Chen–Lih–Wu conjecture [2] about equitable r-colourings of r-regular graphs and towards a list analogue of Hajnal–Szemeredi ´ theorem (see [8] for definitions). Most of our notation is standard; possible exceptions include the following. For a vertex y and set of vertices X, NX(y) := N(y) ∩ X and dX(y) := |NX(y)|. If µ is a function on the edge set, then µ(A, B) := xy∈E(A,B) µ(x, y), where E(A, B) is the set of edges joining a vertex in A to a vertex in B. For a function f : V → Z, the restriction of f to W ⊆ V is denoted by f|W. Functions are viewed formally as sets of ordered pairs. Thus, if u /∈ V then g := f ∪ {(u, γ)} is the extension of f to V ∪ {u} such that g(u) = γ. 2. Main result Let G be a graph with s(r + 1) vertices satisfying ∆(G) r. A nearly equitable (r + 1)-colouring of G is a proper colouring f, whose colour classes all have size s except for one small class V − = V −(f) with size s − 1 and one large class V + = V +(f) with size s + 1. Given such a colouring f, define an auxiliary digraph H = H(G, f) as follows. The vertices of H are the colour classes of f, and a directed edge VW belongs to E(H) if and only if some vertex y ∈ V has no neighbours in W. In this case we say that y is movable to W. Call W ∈ V(H) accessible if V − is reachable from W in H. Note that V − is trivially accessible. Let A = A(f) denote the family of accessible classes, A := A and B := V(G) \ A. Let m := |A| − 1 and q := r − m. Then |A| = (m + 1)s − 1 and |B| = (r − m)s + 1. Let y ∈ B. Since y cannot be moved to A, dA(y) m + 1 and hence dB(y) q − 1. (2.1) Lemma 2.1. If G has a nearly equitable (r + 1)-colouring f whose large class V + is accessible, then G has an equitable (r + 1)-colouring. Proof. Let P := V1 ...Vk be a path in H(G, f) from V1 := V + to Vk := V −. This means that for each j = 1, ... ,k − 1, Vj contains a vertex yj that has no neighbours in Vj+1. So, if we move yj to Vj+1 for j = 1, ... ,k − 1, then we obtain an equitable (r + 1)-colouring of G. Suppose V + ⊆ B. If A = V − then |E(A, B)| r|V −| = r(s − 1) < 1 + rs = |B|, a contradiction to (2.1). Thus m +1= |A| 2. Call a class V ∈ A terminal if V − is reachable from every
A Short Proof of the Hajnal-Szemeredi Theorem on Equitable Colouring 267 class WEV)in the digraph H-V.Trivially,V-is non-terminal.Every non-terminal class W partitionsW)into two parts w andw0,where w is the set of classes that can reach V-in H-W.Choose a non-terminal class U so that:=(is minimal. Then every class in is terminal and no class in has a vertex movable to any class in ()U).Set t:=lo'l and A':=U..Thus every x E A'satisfies d(x)≥m-t. (2.2) Call an edge zy with z∈W∈'andy∈B a solo edge if Nw(y)={z.The ends of the solo edges are called solo vertices and the vertices joined by the solo edges are called special neighbours of each other.Let S.denote the set of special neighbours of z and let Sy denote the set of special neighbours of y in 4'.Let y E B.Since at most r-(m+1+dg(y))colour classes in A have more than one neighbour of y. S≥1-q+1+dav. (2.3) Lemma 2.2.If there exists such that no solo vertex in W is movable to a class in W.then q+1 t.Furthermore,every vertex y E B is solo. Proof.Let S be the set of solo vertices in W and D:=W\S.Then every vertex in Ng(S) has at least one neighbour in W and every vertex in B\Ng(S)has at least two neighbours in W.It follows that |E(W,B)>NB(S)+2(B]-INB(S))).Since no vertex in S is movable. every z∈S satisfies d(e)≤q.By(2.2,every vertex x∈W satisfies da(x)≤t+q.Thus, using s =W=S+Dl qs+qD1+2=2(qs+1)-qS1≤1E(W,B1≤qS1+t+q川D1≤qs+tDL. It follows that q+1≤t.Moreover,.by(2.3)every y∈B satisfies S≥t-q+dsy)≥1. Thus y is solo ◇ Lemma 2.3.There exists a solo Esuch that eitherz is movable to a class in W)or z has two nonadjacent special neighbours in B. Proof.Suppose not.Then by Lemma 2.2 every vertex in B is solo.Moreover,S.is a clique for every solo vertex z e A'.Consider a weight function u on E(A',B)defined by (xy)= if xy is solo. 0 if xy is not solo For z E A'we have u(z,B)=S.li=q if z is solo;otherwise u(z,B)=0.Thus u(A',B) 14-qst.On the other hand.con der y e ∈B.Letc,=max{lSl:z∈S.say cy=ISlz∈ Sy.Using that S:is a clique and (2.1)cy)-1.So cq.Together with (2.3) this yields E员≥号≥u-q+6号=-9g+4≥1 H(A.y)=9 Thus (4',B)tB]=t(gs+1)>qstu(A',B).a contradiction. ◇
A Short Proof of the Hajnal–Szemeredi Theorem on Equitable Colouring ´ 267 class W ∈A\{V} in the digraph H − V. Trivially, V − is non-terminal. Every non-terminal class W partitions A\{W} into two parts SW and TW = ∅, where SW is the set of classes that can reach V − in H − W. Choose a non-terminal class U so that A := TU = ∅ is minimal. Then every class in A is terminal and no class in A has a vertex movable to any class in (A\A ) \ {U}. Set t := |A | and A := A . Thus every x ∈ A satisfies dA(x) m − t. (2.2) Call an edge zy with z ∈ W ∈ A and y ∈ B a solo edge if NW (y) = {z}. The ends of the solo edges are called solo vertices and the vertices joined by the solo edges are called special neighbours of each other. Let Sz denote the set of special neighbours of z and let Sy denote the set of special neighbours of y in A . Let y ∈ B. Since at most r − (m +1+ dB(y)) colour classes in A have more than one neighbour of y, |Sy| t − q +1+ dB(y). (2.3) Lemma 2.2. If there exists W ∈ A such that no solo vertex in W is movable to a class in A\{W}, then q + 1 t. Furthermore, every vertex y ∈ B is solo. Proof. Let S be the set of solo vertices in W and D := W \ S. Then every vertex in NB(S) has at least one neighbour in W and every vertex in B \ NB(S) has at least two neighbours in W. It follows that |E(W,B)| |NB(S)| + 2(|B|−|NB(S))|). Since no vertex in S is movable, every z ∈ S satisfies dB(z) q. By (2.2), every vertex x ∈ W satisfies dB(x) t + q. Thus, using s = |W| = |S| + |D|, qs + q|D| + 2 = 2(qs + 1) − q|S| |E(W,B)| q|S| + (t + q)|D| qs + t|D|. It follows that q + 1 t. Moreover, by (2.3) every y ∈ B satisfies |Sy| t − q + dB(y) 1. Thus y is solo. Lemma 2.3. There exists a solo vertex z ∈ W ∈ A such that either z is movable to a class in A\{W} or z has two nonadjacent special neighbours in B. Proof. Suppose not. Then by Lemma 2.2 every vertex in B is solo. Moreover, Sz is a clique for every solo vertex z ∈ A . Consider a weight function µ on E(A , B) defined by µ(xy) := q |Sx| if xy is solo, 0 if xy is not solo. For z ∈ A we have µ(z,B) = |Sz | q |Sz | = q if z is solo; otherwise µ(z,B)=0. Thus µ(A , B) q|A | = qst. On the other hand, consider y ∈ B. Let cy := max{|Sz | : z ∈ Sy}, say cy = |Sz |, z ∈ Sy. Using that Sz is a clique and (2.1), cy − 1 dB(y) q − 1. So cy q. Together with (2.3) this yields µ(A , y) = z∈Sy q |Sz | |Sy| q cy (t − q + cy) q cy = (t − q) q cy + q t. Thus µ(A , B) t|B| = t(qs + 1) > qst µ(A , B), a contradiction.
268 H.A.Kierstead and A.V.Kostochka We are now ready to prove the Hajnal-Szemeredi theorem. Theorem 2.4.If G is a graph satisfying A(G)<r,then G has an equitable (r+1)-colouring. Proof.We may assume that is divisible byr1.To see this.suppose) p,where p E [r].Let G':=G+KP.Then IG'l is divisible by r +1 and A(G')r.Moreover,the restriction of any equitable(r+1)-colouring of G'to G is an equitable(r+1)-colouring of G. Argue by induction onGl.The base stepG=0is trivial,so consider the induction step lIGll>1.Let e=xy be an edge of G.By the induction hypothesis there exists an equitable (r+1)-colouring fo of G-e.Hence we are done unless some colour class V contains both x and y.Sinced(x)r.there exists another class W such that x is movable to W.Doing so yield a nearly equitable (r +1)-colouring f of G with V-(f)=V\[x)and V+(f)=WU(x).We now show by a secondary induction on q(f)that G has an equitable(r+1)-colouring If +then we are done by Lemma 2.1:in particular,the base step =0holds.Other wise.by Lemma 2.3 there exists a class W E..a solo vertex z E W and a vertex viE S.such that either z is movable to a class XW)or z is not movable in./and there exists another vertex y2S.which is not adjacent to y.By (2.1)and the primary induction hypothesis,there exists an equitable q-colouring g of B-:=By1).Let A+:=AU(y1). Case 1:z is movable to X.Move z to X and yi to W()to obtain a nearly equitable (m+1)-colouring p of A+.Since W(f).V+()=XU().By Lemma 2.1.A+ has an equitable (m+1)-colouring o'.Then o'Ug is an equitable (r+1)-colouring of G. Case 2:z is not movable to any class in..Then d+(z)>d(z)+1>m+1.Thus dg-(=) g-1.So we can move z to a colour class Y B of g to obtain a new colouring g'of B:= B-U(z.Also,move yi to W to obtain an (m 1)-colouring te of A":=V(G)\B'.Set : Ug'.Then is a nea rly equitable colouring of G with AA().Moreover,y2 is movable to w:=WUfy)().Thus q(p')<q(f),and so by the secondary induction hypothesis,G has an equitable(r +1)-colouring " ■ 3.A polynomial algorithm Our proof clearly yields an algorithm.However it may not be immediately clear that its running time is polynomial.The problem lies in the secondary induction,where we may apply Case 2 O(r)times,each time calling the algorithm recursively.Lemma 2.2 is crucial here;it allows us to claim that when we are in Case2(doing much work)we make much progress.As above,G is a graph satistying A(G)s r and G=s(r+1)=:n.Let f be a nearly equitable (r+1)-colouring of G. Theorem 3.1.There exists an algorithm that from input(G,f)constructs an equitable(r+ 1)-colouring of G in c(q +1)n step Proof.We shall show that the construction in the proof of Theorem 2.4 can be accomplished in the stated number of stepsArgue by inductionnThe base stepfollows immediately from Lemma2.1 and the observation that the construction of H and the recolouring can be carriec
268 H. A. Kierstead and A. V. Kostochka We are now ready to prove the Hajnal–Szemeredi theorem. ´ Theorem 2.4. If G is a graph satisfying ∆(G) r, then G has an equitable (r + 1)-colouring. Proof. We may assume that |G| is divisible by r + 1. To see this, suppose that |G| = s(r + 1) − p, where p ∈ [r]. Let G := G + Kp. Then |G | is divisible by r + 1 and ∆(G ) r. Moreover, the restriction of any equitable (r + 1)-colouring of G to G is an equitable (r + 1)-colouring of G. Argue by induction on ||G||. The base step ||G|| = 0 is trivial, so consider the induction step ||G|| 1. Let e = xy be an edge of G. By the induction hypothesis there exists an equitable (r + 1)-colouring f0 of G − e. Hence we are done unless some colour class V contains both x and y. Since d(x) r, there exists another class W such that x is movable to W. Doing so yields a nearly equitable (r + 1)-colouring f of G with V −(f) = V \ {x} and V +(f) = W ∪ {x}. We now show by a secondary induction on q(f) that G has an equitable (r + 1)-colouring. If V + ∈ A then we are done by Lemma 2.1; in particular, the base step q = 0 holds. Otherwise, by Lemma 2.3 there exists a class W ∈ A , a solo vertex z ∈ W and a vertex y1 ∈ Sz such that either z is movable to a class X ∈A\{W} or z is not movable in A and there exists another vertex y2 ∈ Sz , which is not adjacent to y1. By (2.1) and the primary induction hypothesis, there exists an equitable q-colouring g of B− := B \ {y1}. Let A+ := A ∪ {y1}. Case 1: z is movable to X ∈ A. Move z to X and y1 to W \ {z} to obtain a nearly equitable (m + 1)-colouring ϕ of A+. Since W ∈ A (f), V +(ϕ) = X ∪ {z}∈A(ϕ). By Lemma 2.1, A+ has an equitable (m + 1)-colouring ϕ . Then ϕ ∪ g is an equitable (r + 1)-colouring of G. Case 2: z is not movable to any class in A. Then dA+ (z) dA(z)+1 m + 1. Thus dB− (z) q − 1. So we can move z to a colour class Y ⊆ B of g to obtain a new colouring g of B∗ := B− ∪ {z}. Also, move y1 to W to obtain an (m + 1)-colouring ψ of A∗ := V(G) \ B∗. Set ψ := ψ ∪ g . Then ψ is a nearly equitable colouring of G with A∗ ⊆ A(ψ ). Moreover, y2 is movable to W∗ := W ∪ {y1}\{z}. Thus q(ψ ) < q(f), and so by the secondary induction hypothesis, G has an equitable (r + 1)-colouring ψ . 3. A polynomial algorithm Our proof clearly yields an algorithm. However it may not be immediately clear that its running time is polynomial. The problem lies in the secondary induction, where we may apply Case 2 O(r) times, each time calling the algorithm recursively. Lemma 2.2 is crucial here; it allows us to claim that when we are in Case 2 (doing much work) we make much progress. As above, G is a graph satisfying ∆(G) r and |G| = s(r + 1) =: n. Let f be a nearly equitable (r + 1)-colouring of G. Theorem 3.1. There exists an algorithm P that from input (G, f) constructs an equitable (r + 1)-colouring of G in c(q + 1)n3 steps. Proof. We shall show that the construction in the proof of Theorem 2.4 can be accomplished in the stated number of steps. Argue by induction on q. The base step q = 0 follows immediately from Lemma 2.1 and the observation that the construction of H and the recolouring can be carried
A Short Proof of the Hajnal-Szemeredi Theorem on Equitable Colouring 269 out in n steps.Now consider the induction step.In en steps construct,,B.W,z,y1. Using the induction hypothesis on the input(G[B-].fB-).construct the colouring g of B-in c(q(fB-)+1)(qs)3<cqn3 steps.In cn3 steps determine whether Case 1 or Case 2 holds. If Case 1 holds,construct the.This yields an equitable(r+1)- colouring gU o'in a total of icn3 +cqn3 s c(q+1)n3. If Case 2 holds then,by Lemma22.+1.Thus we used onlysteps toconstruct g.Use an additionalcn steps to extend g to.Notice that Wis non-terminal in'.Thus we can choose(')so that A'(')B.If Case I holds for 'then,as above,we can construct an equitable colouring in an steps.So the total number of steps is at most c(+1)n.Otherwise,by Lemma 2.2.g()<.Thus,by the induction hypothesis,we can finish the construction in additional steps.Therefore.the total number of steps is less than c(q +1)n3 ◇ Theorem 3.2.There is an algorithm of complexity O(n)that constructs an equitable(r+ 1)-colouring of any graph G satisfying A(G)<r and G=n. Proof.As above,we may assume that n is divisible by r+1.Let V(G):=1..... Delete all the edges from G to form Go and let fo be an equitable colouring of Go.Now,for i=1.....n-1.do the following. (i)Add back all the edges of G incident with to form Gi. (ii)Ifvhas no neighbours in its colour class in f then setf=f (iii)Otherwise,move v to a colour class that has no neighbours of v to form a nearly equitable colouring f of Gi.Then apply to (Gi,f)to get an equitable (r+1)-colouring fi of Gi. Then fn-1 is an equitable(r+1)-colouring of G-1=G.Since we have only n-1 stages and each stage runs in O(n)steps,the total complexity is (n). Acknowledgemen We would like to thank J.Schmerl for many useful comments. References [1]Blazewicz,J..Ecker,K.Pesch,E Schmidt,G.and Weglarz,J.(2001)Scheduling Computer and Manufacturing Processes,2nd edn,Springer [2]Chen.B.-LLih,K.-W.and Wu.P-L(1994)Equitable coloring and the maximum degree.Europ.. Combin 15 443-447 [3]Erdos,P.(1964)Problem 9.In Theory of Graphs and its Applications (M.Fiedler,ed.).Czech. Academy of Sciences,Prague,p.159. [4]Fan.G.and Kierstead.H.A.(1996)Hamiltonian square paths.J.Combin.Theory Ser.B 67 167-182. [5]Hajnal,A.and Szemeredi,E.(1970)Proof of a conjecture of P.Erdos.In Combinatorial Theory and its Application (P.Erd6s,A.Renyi,and V.T.S6s,eds).North-Holland,London,pp.601-623. [6]Janson,S.and Ruciniski,A.(2002)The infamous upper tail.Random Struct.Alg.20 317-342. [7]Komlos,J.,Sarkozy,G.and Szemeredi.E.(1998)Proof of the Seymour conjecture for large graphs. Ann.Combin.1 43-60
A Short Proof of the Hajnal–Szemeredi Theorem on Equitable Colouring ´ 269 out in 1 4 cn3 steps. Now consider the induction step. In 1 4 cn3 steps construct A,A ,B,W, z, y1. Using the induction hypothesis on the input (G[B−], f|B−), construct the colouring g of B− in c(q(f|B−) + 1)(qs) 3 cqn3 steps. In 1 4 cn3 steps determine whether Case 1 or Case 2 holds. If Case 1 holds, construct the recolouring ϕ in 1 4 cn3 steps. This yields an equitable (r + 1)- colouring g ∪ ϕ in a total of 3 4 cn3 + cqn3 c(q + 1)n3. If Case 2 holds then, by Lemma 2.2, q + 1 t. Thus we used only 1 8 cqn3 steps to construct g. Use an additional 1 4 cn3 steps to extend g to ψ . Notice that W∗ is non-terminal in ψ . Thus we can choose A (ψ ) so that A (ψ ) ⊆ B. If Case 1 holds for ψ then, as above, we can construct an equitable colouring in an additional 1 4 cn3 + 1 8 cqn3 steps. So the total number of steps is at most c(q + 1)n3. Otherwise, by Lemma 2.2, q(ψ ) < 1 2 q. Thus, by the induction hypothesis, we can finish the construction in c qn3 16 additional steps. Therefore, the total number of steps is less than c(q + 1)n3. Theorem 3.2. There is an algorithm P of complexity O(n5) that constructs an equitable (r + 1)-colouring of any graph G satisfying ∆(G) r and |G| = n. Proof. As above, we may assume that n is divisible by r + 1. Let V(G) := {v1, ... ,vn}. Delete all the edges from G to form G0 and let f0 be an equitable colouring of G0. Now, for i = 1, ... ,n − 1, do the following. (i) Add back all the edges of G incident with vi to form Gi. (ii) If vi has no neighbours in its colour class in fi−1, then set fi := fi−1. (iii) Otherwise, move vi to a colour class that has no neighbours of vi to form a nearly equitable colouring f i−1 of Gi. Then apply P to (Gi, f i−1) to get an equitable (r + 1)-colouring fi of Gi. Then fn−1 is an equitable (r + 1)-colouring of Gn−1 = G. Since we have only n − 1 stages and each stage runs in O(n4) steps, the total complexity is O(n5). Acknowledgement We would like to thank J. Schmerl for many useful comments. References [1] Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G. and Weglarz, J. (2001) Scheduling Computer and Manufacturing Processes, 2nd edn, Springer. [2] Chen, B.-L., Lih, K.-W. and Wu, P.-L. (1994) Equitable coloring and the maximum degree. Europ. J. Combin. 15 443–447. [3] Erdos, P. (1964) Problem 9. In ˝ Theory of Graphs and its Applications (M. Fiedler, ed.), Czech. Academy of Sciences, Prague, p. 159. [4] Fan, G. and Kierstead, H. A. (1996) Hamiltonian square paths. J. Combin. Theory Ser. B 67 167–182. [5] Hajnal, A. and Szemeredi, E. (1970) Proof of a conjecture of P. Erd ´ os. In ˝ Combinatorial Theory and its Application (P. Erdos, A. R ˝ enyi, and V. T. S ´ os, eds), North-Holland, London, pp. 601–623. ´ [6] Janson, S. and Rucinski, A. (2002) The infamous upper tail. ´ Random Struct. Alg. 20 317–342. [7] Komlos, J., S ´ ark ´ ozy, G. and Szemer ˝ edi, E. (1998) Proof of the Seymour conjecture for large graphs. ´ Ann. Combin. 1 43–60