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

446 Bor-Liang Chen,Ko-Wei Lih and Pou-Lin Wu have em+n-1.From the condition on y,we know that es3t+2(n-t).We obtain the result by combining these two inequalities. PRooF oF THEOREM 5.Let G be properly colored with three colors.The difference in sizes between the largest and the smallest color classes is called the width of the coloring.The coloring is equitable if the width is 0 or 1.We are going to show that,if the width of a coloring is at least 2,then we always can re-color some of the vertices to decrease the width. Let us start with the three color classes A,B and C,of sizes a,b and c,respectively, such that a≥b≥c and a-c≥2. (1)If there is a vertex x e A3B,then Cx will do.So from now on we assume that A3B=0. (2)Suppose that C3A=.Consider the bipartite subgraph G(A,C)induced by A and C.Since a=c+2 and A3B =☑，there must exist a component G(A',C')of G(A,C)such that A'>C'l.We have 0<A'-C1,by Lemma 6.Hence A']=IC'+1 and A'C'will decrease the width (3)Suppose that B3A=3.Let C3B=t.Similar to step (2),there must exist a component G(A',C')of G(A,C)such that A'>C'l.If IC'3A'st,then we have A'-C'l equal to some t'st+1,by Lemma 6.Choose a subset SC3B such that IS]=t'-1.Then A'C'US will decrease the width since C'and S are disjoint. If |C'3A'=t+1,then we consider the bipartite subgraph G(B,C)induced by B and C.We want to do some re-coloring so that B3A afterwards.If b=c,then BC suffices.Otherwise,since B>C and B3A=,there must exist a component G(B",C")of G(B,C)such that B">C".Since C"3B"C3B]=t,we have B IC"l equal to some t"s+1.Choose a subset S"C3A such that S"=t".Then B"C"US"will do,since C"and S"are disjoint. (4)Now our standing assumptions become A3B=，C3A≠☑andB3A≠⑦ If a=b,then Cx will decrease the width for any vertex xe B3A.Let a>b.If xeB3 4 and y∈A3C, then By and Cx will decrease the width.So we may assume that A3C =3.Then there must exist a component G(A',B')of G(A,B)such that IA'l>' Let B'3A'=and x E B3A.It follows from Lemma 6 that A'=B+1.Then Ccr and A'B'will decrease the width We may henceforth suppose that B'3A'.If there is some xE B'3A'such that one of its neighbors is y satisfying y A'1B',then By and Cx will decrease the width.Therefore,we may further assume that x E B'3A'and y e N(x)imply y eA'2B' for any x and y. Suppose that there are distinct,yB'3Ahaving intersecting neighborhoods.If Nx)=N(y),we first do an exchange B∈z and C←y for any z∈C3A.Then N(x)N(),since otherwise N(x)=N(y)=N(z)would force G=K3.3. This is impossible,since the chromatic number of G was assumed to be 3.So we may suppose that N(x)N(y).Let us choose we C3A and keep it fixed throughout the remaining argument. Now let u∈N(x)∩N(y).If u is not adjacent to w,then B←u,B←wand C,y}will decrease the width.If ue N(w)but there is a third ze B'3A',then u is not adjacent to z and B←w,C←u and C←z will decrease the width, It remains to handle two more cases:(i)every vertex in N(x)nN(y)is adjacent to w and B'3A'=fx,y);(ii)no two distinct x,y e B'3A'have intersecting neighborhoods In the former case,IN(x)UN(y)4 and 2 N(x)nN(y)1.From G(A',B'), delete B3Aand all those vertices which are adjacent to two vertices of BA'Then each remaining vertex will have degree 1 or 2.Hence the resulting graph G'(A',B')

32 JOURNAL OF GRAPH THEORY the hypothetical minimum counter-examples to this conjecture and the structure of "optimal"colorings of such graphs.Using these properties and structure,we show that the Chen-Lih-Wu Conjecture holds for r<4. 2011 Wiley Periodicals.Inc.J Graph Theory 71:31-48.2012 Keywords:equitable coloring:maximum degree 1.INTRODUCTION In some applications of graph coloring.such as the mutual exclusion scheduling problem,scheduling in communication systems,construction timetables,and round- a-clock scheduling (see [1,11,121).there is an additional requirement that color classes be not too larger be of approximately the same size.A model imposing such require ment that by aon ub corin is the follown her H and Szemeredi [3].For a shorter proof see [4]or [8]:for an algorithm see [7]. Theorem 1.For every positive integer r,each graph with A(G)<r has an equitable (r+1)-coloring. r-colorings.Certainly,such graphs are r-colorable and so do not contain the complete graph K+1.Note that if r is odd,then the complete bipartite graph Kr.r has no equitable r-coloring.Chen et al.[2]proposed the following strengthening of Theorem I and Brooks'theorem. Conjecture 2 (Chen et al.[2]).IfG is an r-colorable graph with A(G)<r.then either G has an equitable r-coloring or (G)zr+1 or r=2 and G contains an odd cycle or r is odd and G contains Krr Using Brooks'theorem this is equivalent to: Conjecture 3(Chen et al.[2).IfGis an r-colorable graph with A(G)<r.then either G has an equitable r-coloring or r is odd and G contains Krr. Some partial cases of Conjecture 3 were proved in [2.10.13.14.9].In particular. Chen et al.[2]proved that the conjecture holds forr=3. The aim of this article is twofold:(1)Prove that Conjecture 3 holds for all graphs deree at most four and (foundaion for further Conjecture 3 by deriving some general properties of hypothetical minimum counter- examples to it as well as properties of optimal colorings of such counter-examples. Journal of Graph Theory DOI 10

2 JOURNAL OF GRAPH THEORY the hypothetical minimum counter-examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r ≤4. Keywords: equitable coloring; maximum degree 1. INTRODUCTION In some applications of graph coloring, such as the mutual exclusion scheduling problem, scheduling in communication systems, construction timetables, and rounda-clock scheduling (see [1, 11, 12]), there is an additional requirement that color classes be not too large or be of approximately the same size. A model imposing such requirement is equitable coloring—a proper coloring such that color classes differ in size by at most one. One of the basic results on equitable coloring is the following theorem by Hajnal and Szemeredi [3]. For a shorter proof see [4] or [8]; for an algorithm see [7]. ´ Theorem 1. For every positive integer r, each graph with (G)≤r has an equitable (r+1)-coloring. This theorem has interesting applications in extremal combinatorial and probabilistic problems. It is natural to ask which graphs G with (G)=r≥3 have equitable r-colorings. Certainly, such graphs are r-colorable and so do not contain the complete graph Kr+1. Note that if r is odd, then the complete bipartite graph Kr,r has no equitable r-coloring. Chen et al. [2] proposed the following strengthening of Theorem 1 and Brooks’ theorem. Conjecture 2 (Chen et al. [2]). If G is an r-colorable graph with (G)≤r, then either G has an equitable r-coloring or (G)≥r+1 or r=2 and G contains an odd cycle or r is odd and G contains Kr,r. Using Brooks’ theorem this is equivalent to: Conjecture 3 (Chen et al. [2]). If G is an r-colorable graph with (G)≤r, then either G has an equitable r-coloring or r is odd and G contains Kr,r. Some partial cases of Conjecture 3 were proved in [2, 10, 13, 14, 9]. In particular, Chen et al. [2] proved that the conjecture holds for r=3. Theorem 4 (Chen et al. [2]). Let G be a connected graph with (G)≤3. Then G has no equitable 3-coloring if and only if G=K4 or G=K3,3. The aim of this article is twofold: (1) Prove that Conjecture 3 holds for all graphs with maximum degree at most four and (2) build a foundation for further progress on Conjecture 3 by deriving some general properties of hypothetical minimum counterexamples to it as well as properties of optimal colorings of such counter-examples. Journal of Graph Theory DOI 10.1002/jgt 2011 Wiley Periodicals, Inc. J Graph Theory 71: 31--48, 2012 32 JOURNAL OF GRAPH THEORY

EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 33 The structure of the article is the following.In the next section we prove that minimum counter-examples to Conjecture 3 do not contain certain dense subgraphs.In Sections 3 and 4 we define nearly equitable and optimal nearly equitable colorings of minimum counter-examples to Conjecture 3 and derive some properties of such colorings.In of of The n4.In Section 5 we digress from the main ine todiscuss the following question.If a graph with max imum degree r contains K.it still may have an equitable r-coloring:an example is the graph that consists of two disjoint copies of Krr.Suppose that Conjecture 3 holds for all graphs with maximum degree r and at most sr+I vertices and that H is an (sr+1)-vertex equitably r-colorable graph with maximum degree at most r.The question that we discuss is:Under these conditions.for how many verticesyV(H)could the graph H- y have uitable coloring?The answe is 4 and w use this result to pro e propertie optimal nearly equitable e colorings of min 3.the erive som properties that yield 3 c o C e for all graphs with maximum degree 4. Most of our notation is standard.For example,by A(G).o(G).and y(G)we denote the maximum degree,the clique number,and the chromatic number of a graph G. respectively.All graphs are simple.If S is a set of edges whose ends are in V(G). the n G+S denotes the gnotaionincg on V(G)with edge set E(G)US.Possible deviations fr following. ra graph G.we let G: =IV(G)I.IIGII E(G)I.For a vertex y and set of vertices X.Nx(y):=N(y)nX and dx(y):=INx(y)l.The set of edges of G linking vertices in A to vertices in B is denoted by EG(A,B)or simply by E(A,B).For a set S and element x,we write S+x for Su(x)and S-x for S\[x). For a function f:V-Z.the restriction of f to WcV is denoted by flW.For a positive integer n,the set (1.....n)is denoted by [n]. 2.FORBIDDEN SUBGRAPHS Suppose that Conjecture 3 fails,and let Gbe a counter-example.Then,for some integer r,(G)<r,and if r is odd,then KrG,but G has no equitable r-coloring.We may assume that |Gl is divisible by r,since G will still be a counter-example if we add a disjoint clique of r-(GI mod r)new vertices.Choose r as small as possible;then choose G=(V,E)with |Gl=rs for some integer s with s as small as possible,and subject to this Gll as small as possible.Ther the co jecture holds for H if A(H) also i h△(H nd H lso G does ontain K+l Moreove ontain K:If r is odd this is by hypothesis;if r is even,it is by th minimality of G,since Kr.r.would be a component with an equitable r-coloring.Clearly the conjecture is true for r<2 and for s=1;so r>3 and s22.In the remainder of this section we identify a collection of dense graphs that cannot be contained in our minimum counter-example G. Proposition 5. Gis connected.Furthermore,for all nonempty proper subsets XCV ifX is divisible by r then E(X,V-X)zr. Proof.We shall show that if either staten nt fails,then G has equitable onsider a prope edge cut F:=E(Y1.Y2)with Y2= -Y1.By the mini mality of G there exist equitable r-colorings fi of G[Yil for i=1.2 Journal of Graph Theory DOI 10.1002/jgt

EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 3 The structure of the article is the following. In the next section we prove that minimum counter-examples to Conjecture 3 do not contain certain dense subgraphs. In Sections 3 and 4 we define nearly equitable and optimal nearly equitable colorings of minimum counter-examples to Conjecture 3 and derive some properties of such colorings. In particular, these properties yield a new proof of Theorem 4. In Section 5 we digress from the main line to discuss the following question. If a graph with maximum degree r contains Kr,r, it still may have an equitable r-coloring; an example is the graph that consists of two disjoint copies of Kr,r. Suppose that Conjecture 3 holds for all graphs with maximum degree r and at most sr+1 vertices and that H is an (sr+1)-vertex equitably r-colorable graph with maximum degree at most r. The question that we discuss is: Under these conditions, for how many vertices y∈V(H) could the graph H−y have no equitable r-coloring? The answer is 4, and we use this result to prove more properties of optimal nearly equitable colorings of minimum counter-examples to Conjecture 3. In the last section we derive some properties that yield Conjecture 3 for all graphs with maximum degree 4. Most of our notation is standard. For example, by (G), (G), and (G) we denote the maximum degree, the clique number, and the chromatic number of a graph G, respectively. All graphs are simple. If S is a set of edges whose ends are in V(G), then G+S denotes the graph on V(G) with edge set E(G)∪S. Possible deviations from standard notation include the following. For a graph G, we let |G|:=|V(G)|, G := |E(G)|. For a vertex y and set of vertices X, NX(y):=N(y)∩X and dX(y):=|NX(y)|. The set of edges of G linking vertices in A to vertices in B is denoted by EG(A,B) or simply by E(A,B). For a set S and 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. For a positive integer n, the set {1, ...,n} is denoted by [n]. 2. FORBIDDEN SUBGRAPHS Suppose that Conjecture 3 fails, and let G be a counter-example. Then, for some integer r, (G)≤r, and if r is odd, then Kr,rG, but G has no equitable r-coloring. We may assume that |G| is divisible by r, since G will still be a counter-example if we add a disjoint clique of r−(|G| mod r) new vertices. Choose r as small as possible; then choose G=(V,E) with |G|=rs for some integer s with s as small as possible, and subject to this G as small as possible. Then the conjecture holds for H if (H)<r, and also if both (H)=r and |H|≤|G|−r. Also, G does not contain Kr+1. Moreover, G does not contain Kr,r: If r is odd this is by hypothesis; if r is even, it is by the minimality of G, since Kr,r, would be a component with an equitable r-coloring. Clearly the conjecture is true for r≤2 and for s=1; so r≥3 and s≥2. In the remainder of this section we identify a collection of dense graphs that cannot be contained in our minimum counter-example G. Proposition 5. G is connected. Furthermore, for all nonempty proper subsets X⊂V, if |X| is divisible by r then |E(X,V −X)|≥r. Proof. We shall show that if either statement fails, then G has an equitable r-coloring. Consider a proper edge cut F:=E(Y1,Y2) with Y2=V −Y1. By the minimality of G there exist equitable r-colorings fi of G[Yi] for i=1, 2. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 33