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.