1516 B-L Chen.C-H.Yen/Discrete Mathematics 31(1)151-1517 =21 Theorem 5.2 ()The EACC holds for each connected graph Gwith A(G)3. Th h-e ext,let us consider a graph c Theorem5.4.A graph Gwith A(G)=3x(G)is equitably 3-colorable if and only if exactly one of the following statements holds -3>0. Proof.ByThe rem 2.6.the necessity hold Thus we have ony t rove the suffici e ur nly one2eo2a22生2，。 vbleteuy-e md Theore Then there such that hic to k A(G2)=3>x(G)=2 and IV(G2)I is divisible by 3.then IV(G2)I of G such that the sizes of color classes in nondecreasing order are and +】by using the metho which: h ofthis 2 Th fnd、 3-colorir 1.and G+1.Therefo +g is equitably 3-colorable by lemma 2.4 ThoCde -colrable.respectively.by Theorems 11 and 5 By the statements above.we know that the necessary conditions mentioned in Theorem 2.6 are also sufficient conditions when G satisfies A(G)<3. 6.Some concluding remarks beieve that theofhr6is not ony necessary buso sufitHence,we propose the Coniectmne6lsLatGbeagaptwitha(O≥xO.ThanGsequiabya(O-oorobefamdomfatlkastoneofthefblowims 2.Noatleast tw comGreisomorphictoK 3.Only one compoment of. Therefore,the as the followin. oecr))Thensbe nd on)isodd ny one component of G is isomorphic to KAGA(and a(G-KAGA(G)= 「2X(0 Conjecture 6.3.Let a graph G satisfy A(G)=rx(G).Then G has no equitable r-coloring if and only if r is odd,G hasa subgraph H isomorphic to K and G-H is r-equitable In Chen et al.prove that Conjectures6.2 and 6.3 are equivalent1516 B.-L. Chen, C.-H. Yen / Discrete Mathematics 312 (2012) 1512–1517 Theorem 5.1 ([3], Proof of Theorem 5). Let G be a connected graph with ∆(G) = χ (G) = 3. If the width w of a proper 3-coloring of G is at least 2, then we always can find another proper 3-coloring of G such that whose width is w − 1 or w − 2. Theorem 5.2 ([3]). The E∆CC holds for each connected graph G with ∆(G) ≤ 3. Theorem 5.3 ([2]). Let G be a graph with χ (G) ≥ ∆(G). Then there exists a proper coloring of G using χ (G) colors in which some color class has size α(G). Now, we are ready to obtain our main results. First, a graph G with ∆(G) = 1 ≥ χ (G) does not exist. Second, by Theorem 3.3, we know that a graph G with ∆(G) = 2 ≥ χ (G) is equitably 2-colorable. Next, let us consider a graph G with ∆(G) = 3 ≥ χ (G). Theorem 5.4. A graph G with ∆(G) = 3 ≥ χ (G) is equitably 3-colorable if and only if exactly one of the following statements holds. 1. No components or at least two components of G are isomorphic to K3,3. 2. Only one component of G is isomorphic to K3,3 and α(G − K3,3) > |V(G−K3,3)| 3 > 0. Proof. By Theorem 2.6, the necessity holds. Thus we have only to prove the sufficiency. First, if no components of G are isomorphic to K3,3, then each component of G is equitably 3-colorable by Theorems 1.1 and 5.2. Second, if m components of G are isomorphic to K3,3 for some m ≥ 2, then mK3,3 and the other components of G are equitably 3-colorable, respectively, by Lemma 2.2, Theorems 1.1 and 5.2. Therefore, for each case above, G is equitably 3-colorable by Lemma 2.1. Now, suppose that only one component of G is isomorphic to K3,3, denoted by G1, and α(G − K3,3) > |V(G−K3,3)| 3 > 0. Then there must be one component of G, denoted by G2, such that G2 is not isomorphic to K3,3 and α(G2) > |V(G2)| 3 > 0. If ∆(G2) ≤ 2 or |V(G2)| is not divisible by 3, then G1 + G2 is equitably 3-colorable by lemmas 2.3, 2.5 and Theorem 5.2. If ∆(G2) = 3 > χ (G2) = 2 and |V(G2)| is divisible by 3, then |V(G2)| ≥ 6 and it is not difficult to find a proper 3-coloring of G2 such that the sizes of color classes in nondecreasing order are |V(G2)| 3 − 1, |V(G2)| 3 and |V(G2)| 3 + 1 by using the method mentioned in the proof of Theorem 3.3. Therefore, G1+G2 is equitably 3-colorable by Lemma 2.4. If ∆(G2) = χ (G2) = 3 and |V(G2)| is divisible by 3, then there exists a proper 3-coloring of G2 in which some color class has size α(G2) by Theorem 5.3. Since α(G2) > |V(G2)| 3 , the width of this proper 3-coloring is at least 2. Then we can find another proper 3-coloring of G2 such that the width is equal to 2 by Theorem 5.1 and |V(G2)| is divisible by 3; that is, the sizes of color classes in nondecreasing order are |V(G2)| 3 − 1, |V(G2)| 3 and |V(G2)| 3 + 1. Therefore, G1 + G2 is equitably 3-colorable by Lemma 2.4. Besides, the other components of G, except G1 and G2, are equitably 3-colorable, respectively, by Theorems 1.1 and 5.2. Thus G is equitably 3-colorable by Lemma 2.1. By the statements above, we know that the necessary conditions mentioned in Theorem 2.6 are also sufficient conditions when G satisfies ∆(G) ≤ 3. 6. Some concluding remarks In fact, we believe that the conclusion of Theorem 2.6 is not only necessary but also sufficient. Hence, we propose the following conjecture. Conjecture 6.1. Let G be a graph with ∆(G) ≥ χ (G). Then G is equitably ∆(G)-colorable if and only if 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. Suppose that G is a graph with ∆(G) ≥ χ (G) and only one component of G is isomorphic to K∆(G),∆(G) . If G is isomorphic to K∆(G),∆(G) , then α(G − K∆(G),∆(G)) = 0 = |V(G−K∆(G),∆(G) )| ∆(G) . Otherwise, α(G − K∆(G),∆(G)) ≥ |V(G−K∆(G),∆(G) )| χ (G−K∆(G),∆(G) ) ≥ |V(G−K∆(G),∆(G) )| χ (G) ≥ |V(G−K∆(G),∆(G) )| ∆(G) . Therefore, the conclusion of Conjecture 6.1 also can be equivalently stated as the following conjecture. Conjecture 6.2. Let a graph G satisfy ∆(G) ≥ χ (G). Then G is not equitably ∆(G)-colorable if and only if ∆(G) is odd, only one component of G is isomorphic to K∆(G),∆(G) and α(G − K∆(G),∆(G)) = |V(G−K∆(G),∆(G) )| ∆(G) . Furthermore, Kierstead and Kostochka in [6] also proposed a conjecture to characterize equitable ∆-colorability in which the notion of an r-equitable graph is involved. Let r be a positive integer. A graph G is said to be r-equitable if r ≥ χ (G), |V(G)| is divisible by r and every proper r-coloring of G is equitable. Conjecture 6.3. Let a graph G satisfy ∆(G) = r ≥ χ (G). Then G has no equitable r-coloring if and only if r is odd, G has a subgraph H isomorphic to Kr,r and G − H is r-equitable. In [4], Chen et al. prove that Conjectures 6.2 and 6.3 are equivalent.