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

Discrete Mathematics 312 (2012) 1512–1517 Contents lists available at SciVerse ScienceDirect Discrete Mathematics journal homepage: www.elsevier.com/locate/disc Equitable ∆-coloring of graphs Bor-Liang Chena , Chih-Hung Yenb,∗ a Department of Business Administration, National Taichung Institute of Technology, Taichung 40401, Taiwan b Department of Applied Mathematics, National Chiayi University, Chiayi 60004, Taiwan a r t i c l e i n f o Article history: Available online 14 June 2011 Keywords: Equitable coloring Maximum degree Chromatic number Bipartite graphs Subcubic graphs a b s t r a c t Consider a graph G consisting of a vertex set V(G) and an edge set E(G). Let ∆(G) and χ (G) denote the maximum degree and the chromatic number of G, respectively. We say that G is equitably ∆(G)-colorable if there exists a proper ∆(G)-coloring of G such that the sizes of any two color classes differ by at most one. Obviously, if G is equitably ∆(G)-colorable, then ∆(G) ≥ χ (G). Conversely, even if G satisfies ∆(G) ≥ χ (G), we cannot guarantee that G must be equitably ∆(G)-colorable. In 1994, the Equitable ∆-Coloring Conjecture (E∆CC) asserts that a connected graph G with ∆(G) ≥ χ (G) is equitably ∆(G)-colorable if G is different from K2n+1,2n+1 for all n ≥ 1. In this paper, we give necessary conditions for a graph G (not necessarily connected) with ∆(G) ≥ χ (G)to be equitably ∆(G)-colorable and prove that those necessary conditions are also sufficient conditions when G is a bipartite graph, or G satisfies ∆(G) ≥ |V(G)| 3 + 1, or G satisfies ∆(G) ≤ 3. © 2011 Elsevier B.V. All rights reserved. 1. Introduction A graph G consists of a vertex set V(G) and an edge set E(G). All graphs considered in this paper are finite, loopless, and without multiple edges. We refer the reader to [10] for terminology in graph theory. A proper k-coloring of a graph G is a labeling f : V(G) → {1, 2, . . . , k} such that adjacent vertices have different labels. The labels are colors; the vertices of one color form a color class. The chromatic number of a graph G, written as χ (G), is the least k such that G has a proper k-coloring. An equitable k-coloring of a graph G is a proper k-coloring of G such that the sizes of any two color classes differ by at most one. A graph G is equitably k-colorable if there exists an equitable k-coloring of G. The equitable chromatic number of a graph G, written as χ=(G), is the least k such that G is equitably k-colorable. Obviously, for any graph G, we have χ=(G) ≥ χ (G). In 1973, Meyer [9] introduced first the notion of equitable colorability. In 1998, Lih [7] surveyed the progress on the equitable coloring of graphs. Consider a graph G, and let ∆(G) denote the maximum degree of G. In 1970, one well-known result of Hajnal and Szemerédi implied the following. Theorem 1.1 ([5]). A graph G is equitably k-colorable if k ≥ ∆(G) + 1. Hence, the next thing we would like to know is, when k = ∆(G), whether a graph G is still equitably k-colorable or not. Clearly, if a graph G is equitably ∆(G)-colorable, then ∆(G) ≥ χ (G); otherwise, we have χ=(G) ≤ ∆(G) < χ (G), a contradiction. And in 1941, Brooks proved the following. Theorem 1.2 ([1]). If G is a connected graph different from the odd cycle C2n+1 and the complete graph Kn for all n ≥ 1, then ∆(G) ≥ χ (G). ∗ Corresponding author. Tel.: +886 5 2717873; fax: +886 5 2717869. E-mail address: chyen@mail.ncyu.edu.tw (C.-H. Yen). 0012-365X/$ – see front matter © 2011 Elsevier B.V. All rights reserved. doi:10.1016/j.disc.2011.05.020

B.-L Chen.C.-H.Yen Discrete Mathematics 312(2012)1512-1517 1513 Therefore whe A((C).it is not sufficient to guarantee that C must be equitably A(c)-colorable.Let us considera balanced complete )=2.However,K2n+1.2m+1 is The Eauitable a-Coloring Coniecture (EACC)(131)A connected graph g is equitably a(g)-colorable if G is different from CK.and K for all n>1 ince Alc and A(K). y(K)for all 1 the of the EACC can be equ 1 for all n≥1.But it takes no time to realize that if the graphGwith (C)(G)is disconnected.then the conditions for Gto be uitably e quite different. K3. enGis equitably A(C)-co In this pap rve thatthsere lso sufficent condition when bipartite graphr satisfies△(G> +1.or G satisfies A(G)<3. 2.Preliminaries We list first some notation.Consider a graph G.Leta(G)denote the maximum size of an independent set in G.Moreover. s,the graph ob Dy ta the union denc Lemma 2.1.IftwographsGand H with disjoint vertex sets are bothequitably k-colorable thenGH k-coorabe vise disjoint independent Now.letW 2 UUV-fo L Th chr 11 +三 r an(H) W UWU..-UWr.Moreover.winw;=0and lIWil-IWill I(IUl+IViD)-(IUl+I(IUl-IUiD)+(IVil-IVDI 1 for anyi<j.Therefore,G+H is equitably k-colorable. emma2.2.mKn.is equitably k-colorable for any m≥2，n≥2andk≥2. Proot It is trivial that this lemma holds whenk2.Now assume that3,and let A B,be tbe bipartiuion of the ith component of mK where A.=la and R:=h h m Then V(mK)AUB,where and B UB are independent ets. First,we partition A into pairwise disjoint independent subsets of sizes[. 1.....]and s:partition B into pairwise disjoint independent subsets of sizes. and t.The numbers r.s and t satisfy os r<k-1.0<s<[2mn-r-1]and s+t=2mn=.Next,since IV(mKnn)l 2mn r2mm14「2mm-114 2mn-kt11and 0r2mn-i1r2m Can sho cthIsuTissu if we that the rether with the other inder ndent hat 0 T IBI-IN(S)I- -w(Sl-t≥2n =0:when m≥3 Thus we conclude the proof. roofSince isot divisible byisquablyrblethen Vbe pparwise independent subsetsU.2,.. ..Un such that the sizes ofU.U2. ..U are +1, espectively Furth re.it is not difficult to partition V(Kn)into npairv sets V1.V2 1.respec disjointindepg .le n= Then.fo (G)(Therefore.isqy-colrable Lemma. tthesize ofcoor cses in ondecreaig order are rn-colbrningol -Kn.is equitabl

B.-L. Chen, C.-H. Yen / Discrete Mathematics 312 (2012) 1512–1517 1513 Therefore, a graph G (not necessarily connected) satisfies ∆(G) ≥ χ (G) if and only if no component of G is an odd cycle when ∆(G) = 2 and no component of G is a complete graph of order ∆(G)+1 when ∆(G) ̸= 2. But, even if a graph G satisfies ∆(G) ≥ χ (G), it is not sufficient to guarantee that G must be equitably ∆(G)-colorable. Let us consider a balanced complete bipartite graph K2n+1,2n+1 for some n ≥ 1. Then ∆(K2n+1,2n+1) = 2n + 1 ≥ χ (K2n+1,2n+1) = 2. However, K2n+1,2n+1 is apparently not equitably ∆(K2n+1,2n+1)-colorable. In fact, Chen et al. in 1994 proposed the following conjecture. The Equitable ∆-Coloring Conjecture (E∆CC) ([3]). A connected graph G is equitably ∆(G)-colorable if G is different from C2n+1, Kn and K2n+1,2n+1 for all n ≥ 1. Since ∆(C2n+1) < χ (C2n+1) and ∆(Kn) < χ (Kn) for all n ≥ 1, the conclusion of the E∆CC can be equivalently stated as that a connected graph G with ∆(G) ≥ χ (G) is equitably ∆(G)-colorable if G is different from K2n+1,2n+1 for all n ≥ 1. But, it takes no time to realize that if the graph G with ∆(G) ≥ χ (G) is disconnected, then the conditions for G to be equitably ∆(G)-colorable are quite different. For example, if G is the disjoint union of two K3,3, then G is equitably ∆(G)-colorable. However, if G is the disjoint union of K3,3 and K3, then G is not equitably ∆(G)-colorable. Hence, we need some extra efforts. In this paper, we give necessary conditions for a graph G (not necessarily connected) with ∆(G) ≥ χ (G) to be equitably ∆(G)-colorable and prove that those necessary conditions are also sufficient conditions when G is a bipartite graph, or G satisfies ∆(G) ≥ |V(G)| 3 + 1, or G satisfies ∆(G) ≤ 3. 2. Preliminaries We list first some notation. Consider a graph G. Let α(G) denote the maximum size of an independent set in G. Moreover, let mG denote the graph consisting of m pairwise disjoint copies of G, where m ≥ 1. Besides, for two graphs G and H with disjoint vertex sets, the graph obtained by taking the union of G and H is denoted by G + H. If one component of G is isomorphic to H, then the graph obtained from G by removing such a component is denoted by G − H. Lemma 2.1. If two graphs G and H with disjoint vertex sets are both equitably k-colorable, then G+H is also equitably k-colorable. Proof. Since G and H are both equitably k-colorable, V(G) and V(H) can be partitioned into k pairwise disjoint independent subsets U1, U2, . . . , Uk and V1, V2, . . . , Vk, respectively, such that 0 ≤ |Ui | − |Uj | ≤ 1 and −1 ≤ |Vi | − |Vj | ≤ 0 for any i < j. Now, let Wr = Ur ∪Vr for r = 1, 2, . . . , k. Then Wr is independent for each r ∈ {1, 2, . . . , k} and V(G+H) = V(G)∪V(H) = W1∪W2∪· · ·∪Wk. Moreover, Wi∩Wj = ∅ and ||Wi |−|Wj || = |(|Ui |+|Vi |)−(|Uj |+|Vj |)| = |(|Ui |−|Uj |)+(|Vi |−|Vj |)| ≤ 1 for any i < j. Therefore, G + H is equitably k-colorable. Lemma 2.2. mKn,n is equitably k-colorable for any m ≥ 2, n ≥ 2 and k ≥ 2. Proof. It is trivial that this lemma holds when k = 2. Now, assume that k ≥ 3, and let Ai, Bi be the bipartition of the ith component of mKn,n, where Ai = {a(i−1)n+1, a(i−1)n+2, . . . , ain} and Bi = {b(i−1)n+1, b(i−1)n+2, . . . , bin} for i = 1, 2, . . . , m. Then V(mKn,n) = A ∪ B, where A = A1 ∪ · · · ∪ Am and B = B1 ∪ · · · ∪ Bm are independent sets. First, we partition A into pairwise disjoint independent subsets of sizes ⌈ 2mn k ⌉, ⌈ 2mn−1 k ⌉, . . . , ⌈ 2mn−r k ⌉ and s; partition B into pairwise disjoint independent subsets of sizes ⌈ 2mn−r−1 k ⌉, ⌈ 2mn−r−2 k ⌉, . . . , ⌈ 2mn−k+2 k ⌉ and t. The numbers r, s and t satisfy 0 ≤ r < k − 1, 0 ≤ s < ⌈ 2mn−r−1 k ⌉ and s + t = ⌈ 2mn−k+1 k ⌉ = ⌊ 2mn k ⌋. Next, since |V(mKn,n)| = 2mn = ⌈ 2mn k ⌉ + ⌈ 2mn−1 k ⌉ + · · · + ⌈ 2mn−k+1 k ⌉ and 0 ≤ ⌈ 2mn−i k ⌉ − ⌈ 2mn−j k ⌉ ≤ 1 for any i < j, if we can show that there exist S ⊆ A and T ⊆ B such that |S| = s, |T | = t and S ∪ T is an independent subset, then S ∪ T together with the other independent subsets constitute an equitable k-coloring of mKn,n. Let S = {a1, a2, . . . , as} ⊆ A, and also let N(S) be the set consisting of all vertices in B adjacent to some vertex in S. Note that S = N(S) = ∅ when s = 0. Then there must exist a subset T ⊆ B such that S ∪ T is an independent subset if |B|−|N(S)|−t ≥ 0. And, when m = 2, we have 0 ≤ s, t ≤ n, |N(S)| ≤ n and |B|−|N(S)|−t ≥ 2n−n−n = 0; when m ≥ 3, we have |N(S)| ≤ s+n−1 and |B|−|N(S)|−t ≥ mn−(s+n−1)−t = (m−1)n−(s+t)+1 = (m−1)n−⌊ 2mn k ⌋+1 ≥ 0. Thus we conclude the proof. Lemma 2.3. Let G be a graph and suppose that |V(G)| is not divisible by a positive integer n ≥ 3. If G is equitably n-colorable, then G + Kn,n is also equitably n-colorable. Proof. Since |V(G)| is not divisible by n, if G is equitably n-colorable, then V(G) can be partitioned into n pairwise disjoint independent subsetsU1, U2, . . . , Un such that the sizes ofU1, U2, . . . , Un are ⌊ |V(G)| n ⌋, . . . , ⌊ |V(G)| n ⌋, ⌊ |V(G)| n ⌋+1, . . . , ⌊ |V(G)| n ⌋+ 1, respectively. Furthermore, it is not difficult to partition V(Kn,n)into n pairwise disjoint independent subsets V1, V2, . . . , Vn such that the sizes of V1, V2, . . . , Vn are 3, 2, . . . , 2, 1, respectively. Now, let Wr = Ur ∪ Vr for r = 1, 2, . . . , n. Then, for each r ∈ {1, 2, . . . , n}, Wr is independent and the size of Wr is ⌊ |V(G)| n ⌋ + 3 or ⌊ |V(G)| n ⌋ + 2. Moreover, Wi ∩ Wj = ∅ for any i ̸= j and V(G + Kn,n) = V(G) ∪ V(Kn,n) = W1 ∪ W2 ∪ · · · ∪ Wn. Therefore, G + Kn,n is equitably n-colorable. Lemma 2.4. Let G be a graph and suppose that |V(G)| is divisible by a positive integer n ≥ 3. If there exists a proper n-coloring of G such that the sizes of color classes in nondecreasing order are |V(G)| n − 1, |V(G)| n , . . . , |V(G)| n , |V(G)| n + 1, then G + Kn,n is equitably n-colorable.

1514 B.-L. Chen, C.-H. Yen / Discrete Mathematics 312 (2012) 1512–1517 Proof. It is similar to the proof of Lemma 2.3. Lemma 2.5. Let n ≥ 2 be a positive integer and let G be a graph with ∆(G) ≤ n − 1. Then G + Kn,n is equitably n-colorable if and only if n is even, or G is different from mKn for all m ≥ 1. Proof. (⇒) We prove it by contradiction. Suppose that n is odd and G is equal to mKn for some m. Then α(G) = α(mKn) = m. Since G + Kn,n is equitably n-colorable, V(G + Kn,n) can be partitioned into n pairwise disjoint independent subsets V1, V2, . . . , Vn such that |Vi | = |V(G+Kn,n)| n = |V(mKn+Kn,n)| n = m + 2 for all i ∈ {1, 2, . . . , n}. Moreover, since α(G) = m, we have |Vi ∩V(G)| = m for all i ∈ {1, 2, . . . , n}. Therefore, |Vi ∩V(Kn,n)| = 2 for all i ∈ {1, 2, . . . , n}. This implies that Kn,n is equitably n-colorable. But, it is a contradiction because n is odd. (⇐) First, since ∆(G) ≤ n − 1, G is equitably n-colorable by Theorem 1.1. Hence, if n is even or |V(G)| is not divisible by n, then G + Kn,n is also equitably n-colorable by Lemmas 2.1 and 2.3. Next, let us suppose that n ≥ 3 is odd and |V(G)| is divisible by n. Since G is equitably n-colorable, there is a proper n-coloring of G such that each of color classes, denoted by U1, U2, . . . , Un, has size |V(G)| n . Now, let z be any vertex of G and suppose that z ∈ Ui for some i ∈ {1, 2, . . . , n}. If the open neighborhood NG(z) of z in G satisfies that NG(z) ∩ Uj = ∅ for some j ∈ {1, 2, . . . , n} and j ̸= i, then we can obtain a proper n-coloring of G such that the sizes of color classes in nondecreasing order are |V(G)| n − 1, |V(G)| n , . . . , |V(G)| n , |V(G)| n + 1 by moving z from Ui to Uj . Thus G + Kn,n is equitably n-colorable by Lemma 2.4. Otherwise, NG(z)∩ Uj ̸= ∅ for all j ∈ {1, 2, . . . , n} and j ̸= i. More precisely, since ∆(G) ≤ n − 1, we have |NG(z) ∩ Uj | = 1 for all j ∈ {1, 2, . . . , n} and j ̸= i; that is, G is (n − 1)-regular. Let u ∈ Us and v ∈ Ut be any two different neighbors of z ∈ Ui in G, where {i, s, t} ⊆ {1, 2, . . . , n}. Then s ̸= t and NG(u)∩Ui = NG(v)∩Ui = {z}. If u and v are not adjacent in G, then we can obtain a proper n-coloring of G such that the sizes of color classes in nondecreasing order are |V(G)| n −1, |V(G)| n , . . . , |V(G)| n , |V(G)| n +1 by moving u and v from Us and Ut to Ui and moving z from Ui to Us (or Ut). Thus G + Kn,n is equitably n-colorable by Lemma 2.4. Otherwise, any two different neighbors of z in G are adjacent. It implies that the subgraph of G induced by NG(z)∪ {z} is a complete graph Kn. Since each of the other vertices of Ui has the same property as z, we have that G is mKn, where m = |Ui | = |V(G)| n . But, it is a contradiction. We conclude this section with the following theorem. Theorem 2.6. Let G be a graph with ∆(G) ≥ χ (G). If G is equitably ∆(G)-colorable, then at least one of the following statements holds. 1. ∆(G) is even. 2. No components or at least two components of G are isomorphic to K∆(G),∆(G) . 3. Only one component of G is isomorphic to K∆(G),∆(G) and α(G − K∆(G),∆(G)) > |V(G−K∆(G),∆(G) )| ∆(G) > 0. Proof. We prove it by contradiction. Suppose that ∆(G) is odd, G has only one component isomorphic to K∆(G),∆(G) , denoted by G1, and α(G − K∆(G),∆(G)) ≤ |V(G−K∆(G),∆(G) )| ∆(G) . Since G is equitably ∆(G)-colorable, V(G) can be partitioned into ∆(G) pairwise disjoint independent subsets V1, V2, . . . , V∆(G) . Moreover, since α(G − K∆(G),∆(G)) ≤ |V(G−K∆(G),∆(G) )| ∆(G) , we have |Vi ∩ V(G − K∆(G),∆(G))| = |V(G−K∆(G),∆(G) )| ∆(G) for all i ∈ {1, 2, . . . , ∆(G)}. Therefore, |V(G − K∆(G),∆(G))| and |V(G)| are both divisible by ∆(G). Then |Vi | = |V(G)| ∆(G) = |V(G−K∆(G),∆(G) )|+|V(G1)| ∆(G) = |V(G−K∆(G),∆(G) )| ∆(G) + 2 for all i ∈ {1, 2, . . . , ∆(G)}. However, since |Vi ∩ V(G − K∆(G),∆(G))| = |V(G−K∆(G),∆(G) )| ∆(G) , we know that |Vi ∩ V(G1)| = 2 for all i ∈ {1, 2, . . . , ∆(G)}. This implies that G1 is equitably ∆(G)-colorable. But, it is a contradiction because G1 is isomorphic to K∆(G),∆(G) and ∆(G) is odd. Thus we have the proof. 3. Bipartite graphs In 1996, Lih and Wu proved the following two theorems. Theorem 3.1 ([8]). Let G be a connected bipartite graph with ∆(G) ≥ 2 and bipartition X, Y . If G is different from Kn,n for all n ≥ 2, then there exists an equitable ∆(G)-coloring of G such that at most one color class consists of vertices in X and vertices in Y . Theorem 3.2 ([8]). Kn,n is equitably k-colorable if and only if ⌈n/⌊k/2⌋⌉ − ⌊n/⌈k/2⌉⌋ ≤ 1. In fact, the conclusions in Theorems 3.1 and 3.2 imply that a connected bipartite graph G with ∆(G) ≥ 2 is equitably ∆(G)-colorable if and only if G is different from K2n+1,2n+1 for all n ≥ 1. And we extend this result by removing the connectedness requirement. Theorem 3.3. A bipartite graph G with ∆(G) ≥ 2 is equitably ∆(G)-colorable if and only if G is different from K2n+1,2n+1 for all n ≥ 1. Proof. The necessity is obviously. Thus we have only to prove the sufficiency; that is, if a bipartite graph G with ∆(G) ≥ 2 is different from K2n+1,2n+1 for all n ≥ 1, then G is equitably ∆(G)-colorable. First, if ∆(G) is even or no components of G

B.-L Chen.C.-H.Yen Discrete Mathematics 312(2012)1512-1517 1515 ic toh m>2 the of G are equitably (C)-colorable,respectively.by Lemma 2.Theorems 1.1 and 3.1.Therefore.for each case above.C is equitably A(G)-colorable by Lemma 2.1. Now.suppose that A(G)3 is odd and only one component of Gis isomorphic to K denoted GSince Gis different from K2 for alln>1 and G-KAGAG is still a bipartite graph,we have a(G-KAGAG)> .Then there must be one by such that with isomorphic to K and a(G2)> 0.Without loss of generality.we assume thatY whmG4O1O6m8e8AO6gs品 .1.When △(G2) A(G)and IV(Ga)I is divisible by() dis X by And we can obtain er (G)-cooring of G such that the sizes of coor classes in no nde der are +1by moving one vertex fromS to S2.Hence.G+G2 is equitably A(G)-colorable by Lemma 2.4.If one color class consists of vertices inX and vertices in Y.denoted by S.then there is at least a color classS'X by A(G)>3 ain a proper A(G)-coloring of G2 such that the sizes of color classes in nondecreasing orde an.+1by moving one vertex from S to s'.Hence.G+2 is equitably A(G)-colorable are by Lemma the teoff ave Gand G2.are equitably A(G)-colorable,respectively,by Theorems 1.1 and From the proof of Theorem 3.3.we know that the necessary conditions mentioned in Theorem 2.6 are also sufficient conditions when G is a bipartite graph. 4.A graph G with A(G)=max(x(G),+1 In 1994.Chen et al.proved: Theorem 4.1(3).Let G be a connected graph with A(G)IfG is diferent from K and all n1,then G is equitably A(G-colorable. Later.in 1996.Yap and Zhang put forth a further result. Theorem 4.2 (/11).A connected graph G with l >A(G)>G+1 is equitably A(G)-colorable the connectedness requirement. Theorem 4.3.A graph G with A(G)>maxix(G).+1)is equitably A(G)-colorable if and only if G is different from K2n+1.2n+1 for all n z 1. 品 +1.we have IV(G)<34(G)-3.and hence at most one component of G can be isomorphic to KA(.4().Next,if 1 ofis equitably (C)-colorable. that (G)is odd and co onent of Gis is enoted by G.Since G is rent from fo all n>1 we hays A0≥与andicto水t把收woy >0.Then G=G-KA.+G is equitably A(G)-colorable by From the proof of Theorem 4.3.we know that the necessary conditions mentioned in Theorem 2.6 are also sufficient conditions when G satisfies A(G)>+1. 5.A graph G with3≥A(G)≥X(G coloring of a graph Gfor

B.-L. Chen, C.-H. Yen / Discrete Mathematics 312 (2012) 1512–1517 1515 are isomorphic to K∆(G),∆(G) , then each component of G is equitably ∆(G)-colorable by Theorems 1.1, 3.1 and 3.2. Second, if ∆(G)is odd and m components of G are isomorphic to K∆(G),∆(G) for some m ≥ 2, then mK∆(G),∆(G) and the other components of G are equitably ∆(G)-colorable, respectively, by Lemma 2.2, Theorems 1.1 and 3.1. Therefore, for each case above, G is equitably ∆(G)-colorable by Lemma 2.1. Now, suppose that ∆(G) ≥ 3 is odd and only one component of G is isomorphic to K∆(G),∆(G) , denoted by G1. Since G is different from K2n+1,2n+1 for all n ≥ 1 and G−K∆(G),∆(G) is still a bipartite graph, we have α(G−K∆(G),∆(G)) ≥ |V(G−K∆(G),∆(G) )| 2 > |V(G−K∆(G),∆(G) )| ∆(G) > 0. Then there must be one component of G, denoted by G2, such that G2 with bipartition X, Y is not isomorphic to K∆(G),∆(G) and α(G2) > |V(G2)| ∆(G) > 0. Without loss of generality, we assume that |X| ≥ |Y|. When ∆(G2) ≤ ∆(G) − 1 or |V(G2)| is not divisible by ∆(G), G1 + G2 is equitably ∆(G)-colorable by lemmas 2.3, 2.5 and Theorem 3.1. When ∆(G2) = ∆(G) and |V(G2)| is divisible by ∆(G), there exists an equitable ∆(G)-coloring of G2 such that at most one color class consists of vertices in X and vertices in Y by Theorem 3.1. If no color class consists of vertices in X and vertices in Y, then there are at least two disjoint color classes S1 ⊆ X and S2 ⊆ X by ∆(G) ≥ 3 and |X| ≥ |Y|. And we can obtain a proper ∆(G)-coloring of G2 such that the sizes of color classes in nondecreasing order are |V(G2)| ∆(G) − 1, |V(G2)| ∆(G) , . . . , |V(G2)| ∆(G) , |V(G2)| ∆(G) +1 by moving one vertex from S1 to S2. Hence, G1+G2 is equitably ∆(G)-colorable by Lemma 2.4. If one color class consists of vertices in X and vertices in Y, denoted by S, then there is at least a color class S ′ ⊆ X by ∆(G) ≥ 3 and |X| ≥ |Y|. And we can obtain a proper ∆(G)-coloring of G2 such that the sizes of color classes in nondecreasing order are |V(G2)| ∆(G) − 1, |V(G2)| ∆(G) , . . . , |V(G2)| ∆(G) , |V(G2)| ∆(G) + 1 by moving one vertex from S to S ′ . Hence, G1 + G2 is equitably ∆(G)-colorable by Lemma 2.4. Besides, the other components of G, except G1 and G2, are equitably ∆(G)-colorable, respectively, by Theorems 1.1 and 3.1. Thus G is equitably ∆(G)-colorable by Lemma 2.1. From the proof of Theorem 3.3, we know that the necessary conditions mentioned in Theorem 2.6 are also sufficient conditions when G is a bipartite graph. 4. A graph G with ∆(G) ≥ max{χ(G), |V(G)| 3 + 1} In 1994, Chen et al. proved: Theorem 4.1 ([3]). Let G be a connected graph with ∆(G) ≥ |V(G)| 2 . If G is different from Kn and K2n+1,2n+1 for all n ≥ 1, then G is equitably ∆(G)-colorable. Later, in 1996, Yap and Zhang put forth a further result. Theorem 4.2 ([11]). A connected graph G with |V(G)| 2 > ∆(G) ≥ |V(G)| 3 + 1 is equitably ∆(G)-colorable. In fact, the conclusions in Theorems 4.1 and 4.2 imply that a connected graph G with ∆(G) ≥ max{χ (G), |V(G)| 3 + 1} is equitably ∆(G)-colorable if and only if G is different from K2n+1,2n+1 for all n ≥ 1. And we extend this result by removing the connectedness requirement. Theorem 4.3. A graph G with ∆(G) ≥ max{χ (G), |V(G)| 3 + 1} is equitably ∆(G)-colorable if and only if G is different from K2n+1,2n+1 for all n ≥ 1. Proof. The necessity is obviously. Thus we have only to prove the sufficiency; that is, if a graph G with ∆(G) ≥ max{χ (G), |V(G)| 3 + 1} is different from K2n+1,2n+1 for all n ≥ 1, then G is equitably ∆(G)-colorable. First, since ∆(G) ≥ |V(G)| 3 + 1, we have |V(G)| ≤ 3∆(G) − 3, and hence at most one component of G can be isomorphic to K∆(G),∆(G) . Next, if ∆(G) is even or no components of G are isomorphic to K∆(G),∆(G) , then each component of G is equitably ∆(G)-colorable, respectively, by Theorems 1.1, 4.1 and 4.2. Therefore, G is equitably ∆(G)-colorable by Lemma 2.1. Now, suppose that ∆(G) is odd and only one component of G is isomorphic to K∆(G),∆(G) , denoted by G1. Since G is different from K2n+1,2n+1 for all n ≥ 1, we have ∆(G) ≥ 5 and ∆(G) − 3 ≥ |V(G − K∆(G),∆(G))| ≥ 1, and hence α(G − K∆(G),∆(G)) ≥ 1 > ∆(G)−3 ∆(G) ≥ |V(G−K∆(G),∆(G) )| ∆(G) > 0. Then G = G − K∆(G),∆(G) + G1 is equitably ∆(G)-colorable by ∆(G − K∆(G),∆(G)) < |V(G − K∆(G),∆(G))| ≤ ∆(G) − 3 and Lemma 2.5. From the proof of Theorem 4.3, we know that the necessary conditions mentioned in Theorem 2.6 are also sufficient conditions when G satisfies ∆(G) ≥ |V(G)| 3 + 1. 5. A graph G with 3 ≥ ∆(G) ≥ χ(G) Before we go any further, we need some more definitions. Consider a proper k-coloring of a graph G for some k ≥ χ (G). Then the difference between the maximum size of a color class and the minimum size of a color class is called the width of this proper k-coloring of G. Furthermore, we also need the following theorems for the proof of our main result.