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 equivalent
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.
B.-L Chen.C-H.Yen Discrete Mathematics 312(2012)1512-1517 1517 Acknowledgments The authors thank Professor Ko-Wei Lih,Professor Hung-Lin Fu and the referees for many helpful comments which led References r.J.C n1510 3082008553-5537. Ye A pA A.4.No 70.pp 543
B.-L. Chen, C.-H. Yen / Discrete Mathematics 312 (2012) 1512–1517 1517 Acknowledgments The authors thank Professor Ko-Wei Lih, Professor Hung-Lin Fu and the referees for many helpful comments which led to a better version of this paper. This research was partially supported by the National Science Council of the Republic of China under the grants NSC 95-2119-M-415-001 and NSC 96-2115-M-415-005. References [1] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194–197. [2] B.-L. Chen, K.-C. Huang, C.-H. Yen, Chromatic coloring with a maximum color class, Discrete Math. 308 (2008) 5533–5537. [3] B.-L. Chen, K.-W. Lih, P.-L. Wu, Equitable coloring and the maximum degree, Eur. J. Combin. 15 (1994) 443–447. [4] B.-L. Chen, K.-W. Lih, C.-H. Yen, Equivalence of two conjectures on equitable coloring of graphs (submitted for publication). [5] A. Hajnal, E. Szemerédi, Proof of a conjecture of Erdős, in: A. Rényi, V.T. Sós (Eds.), Combinatorial Theory and Its Applications. Vol. II, in: Colloq. Math. Soc. János Bolyai, vol. 4, North-Holland, Amsterdam, 1970, pp. 601–623. [6] H.A. Kierstead, A.V. Kostochka, Equitable versus nearly equitable coloring and the Chen–Lih–Wu conjecture, Combinatorica 30 (2010) 201–216. [7] K.-W. Lih, The equitable coloring of graphs, in: D.-Z. Du, P.M. Pardalos (Eds.), in: Handbook of Combinatorial Optimization, vol. 3, Kluwer Academic Publishers, 1998, pp. 543–566. [8] K.-W. Lih, P.-L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151 (1996) 155–160. [9] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920–922. [10] D.B. West, Introduction to Graph Theory, second ed., Prentice-Hall, Upper Saddle River, NJ, 2001. [11] H.P. Yap, Y. Zhang, On equitable coloring of graphs, manuscript, 1996
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
圣 Bor-Liang Chen.Ko-Wei Lih and Pou-Lin Wu of vertices in B into red.A one-way arrow AB means that we change the color of B into the A B=ixh and an ind that ea h vertex of I is adjacent to all vertices of H.The complement graph of G is denoted by G. 2.GRAPHS WITH HIGH DEGREES LEMMA 1. Let G be a discon graph.If G is different from (K)and (Knm+2m+y for all m≥1，hcna'(G)>8G. PROOF.Let G,G2,.,G,t≥2，be the components of G.Ifδ(G)=0or 8(G)=1,then the lemma clearly holds.Suppose that 8(G)=2,and hence 8(G)=2 for all i. Consider a longest path in G,and the vertices adjacent to the initial vertex of this path.We see ediately that G contains a cycle of length at least 8(G)+1.(This ment was first ed in Dirac [41.)Thus aG)≥(8(G)+1)/2J≥L(8(G)+1)/2 It ol that a ( G)unless '(G2)-[(a(G)+1)/2]for an even 8(G)- 2m We want to show that this case would force the graph to become (K2+1+).Let x1,x2,...,xam+be a cycle of length 2m +1 in G.If there is an edge uv such that u or v is different from all the x,'s,then a'(G)m+1,which is false.It follows that r,.r,. ..,xm is precisely the vertex set of G.Since the degree of every vertex is at least 2m,G is a copy of Kzm Similarly,G2 is another copy of K2m+1 Hence G turns out to be a(K),which is excluded from the assumptions. LEMMA 2.Let G be nected graph such that G>28(G)+1.If G is not (G)-splittable,then a'(G)>(G). PRooF.For a connected graph G,G>2(G)is sufficient to guarantee the existence of a path P={xo,x1, .x28}of length 28=28(G)(see [2,Exercise 4.2.9)). Hence a'(G)≥6(G). hepah"2zoncpaSlyaMGdeneniahgote8oltynemh the path tside of the path P.The existe follow 1G1>28(G)+1 from the that If y were any x0x23 1x2Y,x2+1x2+2 x2s-x2s would form a mat ing of size However,since the degree of y is at least ,ymust be adja +1,a contradiction to allx2+1,0si<8.Now suppose that x2 and x2y,i j,are adjacent.Then x0r1,,·,,X2/-22-1;X2+2X2+3,·.·,X2-2X2-1;X2+1X2+2,.··,X28-1X28;X2X2iX2i+1y} would form a matching of size +1.So 1=V(G)-(x1,x3,....,x2 is an independent set and each vertex in I is adjacent to all x2s+1,0si<8,i.e.G is 8(G)-splittable.This shows that a'(G)=8(G)could not occur. ■ THEOREM 3.Let G be cted with A(G)G If G is diferent from K and all m1,then G is equitably A(G)-colorable PROOF.Since 4(G)+8(G)=IG]-1 and 4(G)GI/2,we have G>28(G)+1. If G is disconnected,then a'(G)>(G),by Lemma 1.Since G is connected,G cannot be 8(G)-splittable.Furthermore,if G is connected,then a'(G)>8(G),by
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