《图论》课程教学资源（书籍文献）均匀染色相关论文选 Selected papers on the equitable coloring of graphs.pdf_P36-P40

Journal of Combinatorial Theory, Series B 98 (2008) 226–234 www.elsevier.com/locate/jctb An Ore-type theorem on equitable coloring H.A. Kierstead a,1 , A.V. Kostochka b,c,2 a Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287, USA b Department of Mathematics, University of Illinois, Urbana, IL 61801, USA c Institute of Mathematics, Novosibirsk, Russia Received 31 December 2006 Available online 20 August 2007 Abstract A proper vertex coloring of a graph is equitable if the sizes of its color classes differ by at most one. In this paper, we prove that if G is a graph such that for each edge xy ∈ E(G), the sum d(x) + d(y) of the degrees of its ends is at most 2r + 1, then G has an equitable coloring with r + 1 colors. This extends the Hajnal–Szemerédi Theorem on graphs with maximum degree r and a recent conjecture by Kostochka and Yu. We also pose an Ore-type version of the Chen–Lih–Wu Conjecture and prove a very partial case of it. © 2007 Elsevier Inc. All rights reserved. Keywords: Equitable coloring; Ore-type; Packing 1. Introduction An equitable k-coloring of a graph G is a proper k-coloring, for which any two color classes differ in size by at most one. It can be viewed as a packing of G with the |V (G)|-vertex graph, whose components are cliques with either |V (G)|/k or |V (G)|/k vertices. Recall that two n-vertex graphs pack if there exists an edge disjoint placement of these graphs into Kn. In other words, G1 and G2 pack if G1 is isomorphic to a subgraph of the complement of G2 (and vice versa). A number of important graph theoretic problems can be naturally expressed in the language of packing. For example, the classical Dirac’s Theorem [5] on the existence of hamiltonian cycles in each n-vertex graph with minimum degree at least n/2 can be stated in terms of packE-mail addresses: kierstead@asu.edu (H.A. Kierstead), kostochk@math.uiuc.edu (A.V. Kostochka). 1 Research of this author is supported in part by the NSA grant MDA 904-03-1-0007. 2 Research of this author is supported in part by the NSF grants DMS-0400498 and DMS-06-50784 and by grant 06-01-00694 of the Russian Foundation for Basic Research. 0095-8956/$ – see front matter © 2007 Elsevier Inc. All rights reserved. doi:10.1016/j.jctb.2007.07.003

H.A.Kierstead.A.V.Kostochka/Journal of Combinatorial Theory.Series B98 (2008)226-234 227 ing as follows:Let n3.If G is an n-vertex graph and its maximum degree.A(G).is at most in-1,then G packs with the cycle Cn of length n. Similarly,Ore's theorem [14]on hamiltonian cycles is as follows:If n3 and G is an n vertex graph with dd(y) -2for each(G).then Gpackswith the eycle C One of the main known results on equitable coloring is the Hajnal-Szemeredi Theorem [6] stating that every graph with maximum degree A(G)<r has an equitable (r+1)-coloring.It has many applications.Alon and Furedi [1].Alon and Yuster [2.31.Janson and Rucinski [7]. Pemma araju [15],and Rodl and Ruciriski [16]used this theorem to derive boun nds for sums dependent random variables with limited dependence or to prove the existence of some special vertex partitions of graphs and hypergraphs.We call the Hajnal-Szemeredi Theorem a Dirac- type result,since it provides a packing of a graph G with a special graph given a restriction on the maximum degree of G.Recently,Kostoc a and Yu [11.12]conjectured that the following Ore-type result holds true:Every graph in which d(x)+d(y)<2r for every edge xy has an equitable (r+1)-coloring.Clearly,this conjecture implies the Hajnal-Szemeredi Theorem.In this paper,we prove the following somewhat stronger result. Theorem 1.Every graph satisfying d(x)+d(y)<2r+1 for every edge xy,has an equitable (r +1)-coloring. The proof elaborates the ideas of the original proof of the Hajnal-Szemeredi Theorem [6]and of the recent short proof of it in []Notice that if the bound on maximum degree is weakened from 2r +1 to 2r +2,then it is satisfied by Kr+2 which does not have any (r+1)-coloring. More subtly,K also satisfies the weakened bound,but ifr+1 is odd,then it does not have an equitable olo ing:so the HajnalSzemeredi Theorem is tight.Of couse these graphs also show that Theorem 1 is tight.Replacingr+1 in the previous discussion byr,Chen,Lih and Wu [4]proposed the following analogue of Brooks'Theorem for equitable coloring: Conjecture 2.(See (41.)Let G be c connected raph with△(G)≤r.If G has no equitable r-coloring,then either G is an odd cycle,or G=K+orr is odd and G=K.r There are more graphs for which Theorem 1 is tight,than those for which the Hajnal- equitable(r+1)-coloring.We conjecture that the following Ore-type analogue of the Chen-Lih-Wu Conjecture holds(again we replace r +1 by r). Conjecture 3.Let r23.If G is a graph satisfying d(x)+d(y)<2r for every edge xy.and G has no equitable r-coloring,then G contains either Kr or Km.2r-m for some odd m. We also prove that Conjecture 3 holds forr The structure of the text is as follows.In the next section we prove Theorem 1.The key ingredients of the proof are a recoloring lemma and a discharging proof of the nonexistence of a bad example.In the last section we discuss the Chen-Lih-Wu Conjecture and its extension, Coniecture 3 Most of our notation is standard;possible exceptions include the following.For a graph G=(V,E),we let IGI :IVI,IIGll :IEl and (G):=max(d(x)+d(y):xy EE).For a ver- tex v and set of vertices X,Nx(v):=[x EX:vx EE)and dx(v):=INx(v)I.As usual,N(v)=

H.A. Kierstead, A.V. Kostochka / Journal of Combinatorial Theory, Series B 98 (2008) 226–234 227 ing as follows: Let n 3. If G is an n-vertex graph and its maximum degree, Δ(G), is at most 1 2n − 1, then G packs with the cycle Cn of length n. Similarly, Ore’s theorem [14] on hamiltonian cycles is as follows: If n 3 and G is an nvertex graph with d(x)+d(y) n−2 for each edge xy ∈ E(G), then G packs with the cycle Cn. One of the main known results on equitable coloring is the Hajnal–Szemerédi Theorem [6] stating that every graph with maximum degree Δ(G) r has an equitable (r + 1)-coloring. It has many applications. Alon and Füredi [1], Alon and Yuster [2,3], Janson and Rucinski [7], ´ Pemmaraju [15], and Rödl and Rucinski [16] used this theorem to derive bounds for sums of ´ dependent random variables with limited dependence or to prove the existence of some special vertex partitions of graphs and hypergraphs. We call the Hajnal–Szemerédi Theorem a Diractype result, since it provides a packing of a graph G with a special graph given a restriction on the maximum degree of G. Recently, Kostochka and Yu [11,12] conjectured that the following Ore-type result holds true: Every graph in which d(x) + d(y) 2r for every edge xy has an equitable (r + 1)-coloring. Clearly, this conjecture implies the Hajnal–Szemerédi Theorem. In this paper, we prove the following somewhat stronger result. Theorem 1. Every graph satisfying d(x) + d(y) 2r + 1 for every edge xy, has an equitable (r + 1)-coloring. The proof elaborates the ideas of the original proof of the Hajnal–Szemerédi Theorem [6] and of the recent short proof of it in [8]. Notice that if the bound on maximum degree is weakened from 2r + 1 to 2r + 2, then it is satisfied by Kr+2 which does not have any (r + 1)-coloring. More subtly, Kr+1,r+1 also satisfies the weakened bound, but if r + 1 is odd, then it does not have an equitable r-coloring; so the Hajnal–Szemerédi Theorem is tight. Of course, these graphs also show that Theorem 1 is tight. Replacing r + 1 in the previous discussion by r, Chen, Lih and Wu [4] proposed the following analogue of Brooks’ Theorem for equitable coloring: Conjecture 2. (See [4].) Let G be a connected graph with Δ(G) r. If G has no equitable r-coloring, then either G is an odd cycle, or G = Kr+1, or r is odd and G = Kr,r. There are more graphs for which Theorem 1 is tight, than those for which the Hajnal– Szemerédi Theorem is tight. For example, for each odd m<r +1, the graph Km,2r+2−m satisfies the condition d(x) + d(y) 2r + 2 for every edge xy and has no equitable (r + 1)-coloring. We conjecture that the following Ore-type analogue of the Chen–Lih–Wu Conjecture holds (again we replace r + 1 by r). Conjecture 3. Let r 3. If G is a graph satisfying d(x) + d(y) 2r for every edge xy, and G has no equitable r-coloring, then G contains either Kr+1 or Km,2r−m for some odd m. We also prove that Conjecture 3 holds for r = 3. The structure of the text is as follows. In the next section we prove Theorem 1. The key ingredients of the proof are a recoloring lemma and a discharging proof of the nonexistence of a bad example. In the last section we discuss the Chen–Lih–Wu Conjecture and its extension, Conjecture 3. Most of our notation is standard; possible exceptions include the following. For a graph G = (V,E), we let |G| := |V |, G := |E| and σ(G) ¯ := max{d(x) + d(y): xy ∈ E}. For a vertex v and set of vertices X, NX(v) := {x ∈ X: vx ∈ E} and dX(v) := |NX(v)|. As usual, N(v) =

228 H.A.Kierstead.A.V.Kostochka/Joumal of Combinatorial Theory.Series B98(2008)226-234 n8 element x,we write S+x for SU(x)and S-x for S\x).For a function f:VZ,the restric tion of f to WV is denoted by flW.Functions are viewed formally as sets of ordered pairs. 2.Main proof In this section we prove Theorem 1.For r=0 the statement is obvious.Suppose that r>1 and that the theorem holds for all 0r'<r.Let G be a graph satisfying G(G)<2r+1.We may assume that |G is divisible by r+1.To see this,su se that |GI=s(r +1)-p,where pE[r].Let G'be the disjoint union of G and Kp.Then IG'l is divisible byr+1 and(G) Moreover,the restriction of any equitable (r+1)-coloring of G'to G is an equitable (r+1)- coloring of G.So let IGl=(r+1)s. Suppose.that ed-minimal.Con- sider any edgee=xy withd(x)sd(y).By minimality,there exists an equitable(r+1)-coloring of G-e.Since G is a counterexample.some color class V contains both x and v.Since G(G)<2r+1,d(x)r.Thus there exists a class W such that x has no neighbors in W Moving x to W yields an (r+1)-coloring f of G with all classes of size s,except for one small class V-(f) x of size s- and one large class +(f)=W+x of size s+1.We say that such a coloring is nearly equitable. Given a coloring f with a unique small class V-(but possibly no large class),define an auxiliary digraph=H(f)as follows.The vertices of H are the color classes of f.A directed edge UW belongs to E(H)iff some vertex yU has no neighbors in W.In this case we say that y is movable to W.Call WeV(H)accessible,if V-is reachable from W in H.So V-is trivially accessible. Lemma 4.If G has a nearly equitable coloring.whose large class V+is accessible,then it has an equitable coloring with the same number of colors. Proof.Let P=V .Ve be a path in H from V:=V+to V:=V-.This means that for eachj=1. ,k .1,Vj con sa vertexy that has no neighbors in V+So,if we move yi to Vi+i for j=1.....k-1,then we obtain an equitable coloring with the same number of color classes. Let A Af)denote the family of accessible classes and B denote the family of non accessible classes.Then V-EA and,by Lemma 4.V+E B.Set A:=UA,B:=UB m :=Al-1 and g :=1B]=r-m.Then Al=(m +1)s-1 and Bl=gs +1. Each vertex y B has a neighbor in each class of A and so satisfies da(y)m+1.(1) It follows that 6(G[B])≤6(G)-2(m+1)≤2g-1. Thus by the minimality of r. Every subgraph of G[B]has an equitable q-coloring. For an accessible class UA(f),define Sy:=Su(f)to be the set of classes XA such that there is an X,V--path in H(f)-U and TU :Tu(f):=A\(Sv+U).Call U terminal,if

228 H.A. Kierstead, A.V. Kostochka / Journal of Combinatorial Theory, Series B 98 (2008) 226–234 NV (v). If μ is a function on edges, then μ(A,B) := xy∈E(A,B) μ(x,y), where E(X,Y) := {xy: x ∈ X and y ∈ Y}. If G is a directed graph then E−(X) := E(V \ X,X}. For a set S and an element x, we write S +x for S ∪{x} and S −x for S \{x}. 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. 2. Main proof In this section we prove Theorem 1. For r = 0 the statement is obvious. Suppose that r 1 and that the theorem holds for all 0 r < r. Let G be a graph satisfying σ(G) ¯ 2r + 1. 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 be the disjoint union of G and Kp. Then |G | is divisible by r +1 and σ(G¯ ) r. Moreover, the restriction of any equitable (r + 1)-coloring of G to G is an equitable (r + 1)- coloring of G. So let |G| = (r + 1)s. Suppose for a contradiction, that G is an edge-minimal counterexample to the theorem. Consider any edge e = xy with d(x) d(y). By minimality, there exists an equitable (r +1)-coloring of G − e. Since G is a counterexample, some color class V contains both x and y. Since σ(G) ¯ 2r + 1, d(x) r. Thus there exists a class W such that x has no neighbors in W. Moving x to W yields an (r + 1)-coloring f of G with all classes of size s, except for one small class V −(f ) = V − x of size s − 1 and one large class V +(f ) = W + x of size s + 1. We say that such a coloring is nearly equitable. Given a coloring f with a unique small class V − (but possibly no large class), define an auxiliary digraph H = H(f ) as follows. The vertices of H are the color classes of f . A directed edge UW belongs to E(H) iff some vertex y ∈ U has no neighbors 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. So V − is trivially accessible. Lemma 4. If G has a nearly equitable coloring, whose large class V + is accessible, then it has an equitable coloring with the same number of colors. Proof. Let P = V1,...,Vk be a path in H from V1 := V + to Vk := V −. This means that for each j = 1,...,k − 1, Vj contains a vertex yj that has no neighbors in Vj+1. So, if we move yj to Vj+1 for j = 1,...,k − 1, then we obtain an equitable coloring with the same number of color classes. ✷ Let A = A(f ) denote the family of accessible classes and B denote the family of nonaccessible classes. Then V − ∈ A and, by Lemma 4, V + ∈ B. Set A := A, B := B, m := |A| − 1 and q := |B| = r − m. Then |A| = (m + 1)s − 1 and |B| = qs + 1. Each vertex y ∈ B has a neighbor in each class of A and so satisfies dA(y) m + 1. (1) It follows that σ¯ G[B] σ(G) ¯ − 2(m + 1) 2q − 1. Thus by the minimality of r, Every subgraph of G[B] has an equitable q-coloring. (2) For an accessible class U ∈ A(f ), define SU := SU (f ) to be the set of classes X ∈ A such that there is an X,V −-path in H(f )−U and TU := TU (f ) := A\ (SU +U). Call U terminal, if

H.A.Kierstead.A.V.Kostochka/Journal of Combinatorial Theory.Series B 98(2008)226-234 229 S=A-U:otherwise U is non-terminal.Note that if U is non-terminal then T.Trivially, V-is non-terminal unless=0.in which case it is terminal. Define a non-empty family A:=A(fA(f)as follows.If m-0 then set A':=A- (V-).Other e v WIS is a non-tern minal clas and so such classe ist.Choose a non-term inalU so that ITul is minimum and set A':=TU.Let A':=A'(f):=A'and t:=t(f):=A'l. Lemma 5.The family A'satisfies the following: (P1)Every class in A'is terminal P2)dA(x)≥m-t for allx∈A' Proof.If m=0 then the only accessible class V-is terminal.So A'=A satisfies(P1)and(P2) trivially.Otherwise m>0 and A'=Tu for some non-terminal UEA.Consider X E TU.Then Tx CTU.By the minimality of Tu,X is terminal.So(P1)holds true. No class in A'=Tu has an out-neighbor in Su.It follows that every vertex in A'has a neighbor in each of the m-t classes of Sy.So (P2)holds true. An edge zy is solo ifzWA',y B and Nw(y)=(z).The ends of solo edges are called solo vertices and vertices linked by solo edges are called special neighbors of each other. Our interest in terminal classes and solo edges stems from the following lemma Lemma 6.Suppose that We A'.IfzE W is solo then z has a neighbor in every class of A-W. In particular dA(a)≥m. Proof.Suppose for a contradiction that z has a special neighbor y B and no neighbor in Xe A-W Si ce W is terminal,there exists a path P from X to v-in H-W.Move z to X and X*:=X+z is independent and,since xy is solo,W*:=W+y- peyields eqtb coon了产ofGA+ywi油V+9）=X+2 Moreover p*:=P+V+(f*)-X is a path from V+(f*)to V-(f*)in H(f*).By Lemma 4. G[A+y]has an equitable (m+1)-coloring h.By(2).G[B]-y has an equitable q-coloring h2 Thush is an equitable (r+1)-coloring of G,a contradiction. We now come to a delicate point in the argument.Define an obstruction to be a nearly equi- table (r+1)-coloring f such that (C1)m(f)=A(f)|-1 is maximum;and (C2)subiect to(Cl).t(f)=A(f)lis minimum. Given an obstruction f,the next lemma allows us to switch the colors of the ends of a solo edge to obtain a new obstruction.When this operation is applied in the proof of Claim 10,we consider two cases depending on whether tq.It is important that after switching,we are still in the same case.This is guaranteed by conditions(C1)and(C2). Lemma 7.Suppose that f is an obstruction,We A'and z E W is a solo vertex with a special neighbor y E B.Set A-:=A-z.Then G has an obstruction g such that gIA-=flA-and g(y)=f(z). (3)

H.A. Kierstead, A.V. Kostochka / Journal of Combinatorial Theory, Series B 98 (2008) 226–234 229 SU = A−U; otherwise U is non-terminal. Note that if U is non-terminal then TU = ∅. Trivially, V − is non-terminal unless m = 0, in which case it is terminal. Define a non-empty family A := A (f ) ⊆ A(f ) as follows. If m = 0 then set A := A = {V −}. Otherwise, V − is a non-terminal class, and so such classes exist. Choose a non-terminal U so that |TU | is minimum and set A := TU . Let A := A (f ) := A and t := t(f ) := |A |. Lemma 5. The family A satisfies the following: (P1) Every class in A is terminal. (P2) dA(x) m − t for all x ∈ A . Proof. If m = 0 then the only accessible class V − is terminal. So A = A satisfies (P1) and (P2) trivially. Otherwise m > 0 and A = TU for some non-terminal U ∈ A. Consider X ∈ TU . Then TX ⊂ TU . By the minimality of TU , X is terminal. So (P1) holds true. No class in A = TU has an out-neighbor in SU . It follows that every vertex in A has a neighbor in each of the m − t classes of SU . So (P2) holds true. ✷ An edge zy is solo if z ∈ W ∈ A , y ∈ B and NW (y) = {z}. The ends of solo edges are called solo vertices and vertices linked by solo edges are called special neighbors of each other. Our interest in terminal classes and solo edges stems from the following lemma. Lemma 6. Suppose that W ∈ A . If z ∈ W is solo then z has a neighbor in every class of A− W. In particular dA(z) m. Proof. Suppose for a contradiction that z has a special neighbor y ∈ B and no neighbor in X ∈ A − W. Since W is terminal, there exists a path P from X to V − in H − W. Move z to X and y to W. By hypothesis X∗ := X + z is independent and, since xy is solo, W∗ := W + y − z is independent. This yields a nearly equitable coloring f ∗ of G[A + y] with V +(f ∗) = X + z. Moreover P∗ := P + V +(f ∗) − X is a path from V +(f ∗) to V −(f ∗) in H(f ∗). By Lemma 4, G[A+y] has an equitable (m+1)-coloring h1. By (2), G[B]−y has an equitable q-coloring h2. Thus h1 ∪ h2 is an equitable (r + 1)-coloring of G, a contradiction. ✷ We now come to a delicate point in the argument. Define an obstruction to be a nearly equitable (r + 1)-coloring f such that (C1) m(f ) = |A(f )| − 1 is maximum; and (C2) subject to (C1), t(f ) = |A (f )| is minimum. Given an obstruction f , the next lemma allows us to switch the colors of the ends of a solo edge to obtain a new obstruction. When this operation is applied in the proof of Claim 10, we consider two cases depending on whether t q. It is important that after switching, we are still in the same case. This is guaranteed by conditions (C1) and (C2). Lemma 7. Suppose that f is an obstruction, W ∈ A and z ∈ W is a solo vertex with a special neighbor y ∈ B. Set A− := A − z. Then G has an obstruction g such that g|A− = f |A− and g(y) = f (z). (3)