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