1514 B-L Chen.C-H.Yen/Discrete Mathematics 3(1)1512-1517 Proof.It is similar to the proof of Lemma 2.3. Lemma25 let n>2 hea and let G he c y n-c V(G+K) that. be partit f,since n).Therefore =m 2 fo is odd (Eirst si by Theorem 1.1.Hence,ifn is even or V(G)is not divisible by n.then Gis also equitably n-colorable by Lemmas 2.1 and 2.3.Next,let us suppose that n3is odd and (is divisible by n.SinceGisequitably n-oorable.there isa proper 作h and ia i th CanObiihSepenneigborhodNetaofzin uch tha the +1 by n equitably n-colorable by Lemma 2.4.Otherwise.Nc()for all j(1.2 m U:to U.T GK n)andi≠i.More since A(G) 1 we e INc(z)nU 1 for allj(1. )-regula Nc(v)nU here (i.s.t1,2 that and and U.tol an ving z fro om U:to U.(or U.)Thus G+K is equ tably n-colorable by Lemma 2.4.Otherwise. vo different r V he ume ppy otn ▣ We conclude this section with the following theorem Let bet)(-colbe the least one ohellwingsttemet 3.Only one component of G is isomorphic to KAG.and a(G-KAG.G)> c 0. by GI.and (G-KA(G)AG)< Since G is equitably A(G)-colorable,V(G)can be partitioned into A(G) pairwise disjoint independent subsets V.Moreover,since a(G-K we have divisible by A(G).ThenV= .IV(G-Kacc IV(G-K forl1.(G)).However. since(G we know that)-for. A(G))This implies 3.Bipartite graphs In 1996.Lih and Wu proved the following two theorems then there r class consists of vertices in Theorem 3.2 ()Kn.is equitably k-colorable if and only if [n/Lk/2-n/Tk/21]1 In fact,the conclusions in Theorems 3.1 and 3.2 imply that a connected bipartite graph G with A(G)>2 is equitably A(G)-colorable if and only if G is different fromK for all n 1.And we extend this result by removing the necteaness requiremer msem3.A咖arie8"phwith (C)≥2 quito的4 oon onl在d脉erntom Proof.The necessity is obviously.Thus we have only to prove the sufficiency:that is,if a bipartite graph Gwith A(G)22 is different from K2+1.+for all n>1.then G is equitably A(G)-colorable.First,if A(G)is even or no components of G1514 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