《图论》课程教学资源（书籍文献）均匀染色相关论文选 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)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.

1516 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.

Europ.J.Combinatorics (1994)15,443-447 Equitable Coloring and the Maximum Degree BOR-LIANG CHEN,Ko-WEI LIH AND POU-LIN WU and K for all m.This conjecture is established for graphs G satisfying 4G≥G/2or'4G)s3. 1.INTRODUCTION All graphs and without multiple edges.A graph G (G).E(G)is said to be,loopless an ( y k-colorable e if the vertex set V(G)can be partitioned into k independent subsets V,V2,....V such that1 for all i and j.Each V is said to form a color class.The smallest integer k for which G is equitably k-colorable is called the equitable chromatic number of G,denoted by (G).W.Meyer [7]introduced this notion of equitable colorability.Let 4(G)denote the maximum degree of the graph G.An earlier work of Hajnal and Szemeredi [5] implied that a graph G is equitably k-colorable if k>A(G).Meyer proposed the conjecture that x-(G)sA(G)for any connected graph G which is neither a complete graph K nor an odd cycle C Recently,Lih and Wu [6]proved that Meyer's coniecture is true for connected bipartite graphs.They actually showed that a connected bipartite graph G is equitably A(G)-colorable if G is different from the for all m≥0.In Chen and Lih I31.a formula for ic nu as dete in Bo nd Gr ally prompts us to put fo rth the is paper THE EoUrTABLE 4-COLORING CONECTURE.A connected graph G is equitably 4(G)-colorable if it is different from K.C and K2 m+1.2m+1 for all m≥1. Since x(K2m+12m1)=2,this conjecture implies Meyer's conjecture.We are going to prove this conjecture for the case 4(G)=G/2,where GI denotes the number of vertices of G.We will show that it suffices to establish the equitable 4-coloring conjecture for regular graphs.A proof for the case of cubic graphs then follows. We now list some notation and definitions.Let LxJ denote the largest integer not greater than x.Let deg(v)be the degree of the vertex v.We use 8(G)and a'(G)to denote,respectively,the smallest degree and the largest size of a matching (i.e nonincident edges)in the graph G.The (open)neighborhood N(v)of a vertex v consists of all vertices adjacent to v.A bipartit raph G is ofter ssed as G(X,Y), with the two parts and yex G)Any bipartite graph (X'yi is usually use ed to aspres nsidered in this paper is at least one osets es of the graph G.For a nonnegative inte set{女 ∈A x is adj in th the acent to exa actly k verti r飞le he (and are ed wi me c say red,(respe say blue notation ABmeans that we change the color of vertices in A into blue and the colo 443 0195-6698/94/050443+05308.00/0 1994 Academic Press Limited

Equitable coloring 445 Lemma 2.It follows that a'(G)GI-A(G).We first use G]-A(G)colors to color 2(Gi-A(G))vertices such that each color class consists of two vertices.Each of the remaining 24(G)-GI vertices is colored with a different color.There are 4(G)colors used in total.The cardinality of each color class is either 1 or 2. ■ 3.REGULAR GRAPHS SUFFICE For pos ng on whe integer out as the so-called feelers. For n=2t,take two copies of K with one copy on the vertex set (u1,u2,...,un and another copy on the vertex set fv,,v2,...,vnl.Connect each u with v by an edge for 2sisn.Then connect u with a new vertex x and connect v with another new vertex y.Both x and y are called feelers.Except the feelers,the degree of each vertex is equal to n For the casen2-1,take three copies of Ko the vertex sets u (.a d spectively.Co ect r1≤i tv:with w and connect w with u let u,be adjacent to the unique feeler vertex x.Except for the feeler,the degree of each vertex is equal to n in this case too. THEOREM 4.The equitable A-coloring conjecture is true if it holds for all regular graphs. PROoF.Let G be a nonregular connected graph.If 4(G)=n is odd,to each vertex v we attach A(G) deg(v)c opics of byide ertex mak any copie ng th vith v in A(G)-1.How rder to 4(G)0 ever,the number or vertices of degree 4(G)- is eve en.In the second stage,we attach further copies of H to the graph by identifying the two feelers to different vertices.We finally arrive at an inflated graph G*which is regular of degree n Suppose that the conjecture holds for G+,i.e.G*is equitably n-colorable.Since H was constructed out of copies of K,an equitable n-coloring of G is induced from that of G*when those additional vertices are removed. ■ 4.CUBIC GRAPHS omatic n umber of the the equ abl ture has already tablishe for G.Hence the validity of the conjecture for all cubic graphs follows from the next theorem. THEOREM 5.Let G be a connected cubic graph,the chromatic number of which is 3. Then x_(G)=3. We need a technical lemma for the proof of this theorem LEMMA 6 Let G(x y)be and A(G))3.fY3=1,then m onnected bipartite graph such that X=mn=Y -n≤t+1 PROOF. Let e be the number of edges of G(X,)Since G(X,Y)is connected,we