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.