32 JOURNAL OF GRAPH THEORY the hypothetical minimum counter-examples to this conjecture and the structure of "optimal"colorings of such graphs.Using these properties and structure,we show that the Chen-Lih-Wu Conjecture holds for r<4. 2011 Wiley Periodicals.Inc.J Graph Theory 71:31-48.2012 Keywords:equitable coloring:maximum degree 1.INTRODUCTION In some applications of graph coloring.such as the mutual exclusion scheduling problem,scheduling in communication systems,construction timetables,and round- a-clock scheduling (see [1,11,121).there is an additional requirement that color classes be not too larger be of approximately the same size.A model imposing such require ment that by aon ub corin is the follown her H and Szemeredi [3].For a shorter proof see [4]or [8]:for an algorithm see [7]. Theorem 1.For every positive integer r,each graph with A(G)<r has an equitable (r+1)-coloring. r-colorings.Certainly,such graphs are r-colorable and so do not contain the complete graph K+1.Note that if r is odd,then the complete bipartite graph Kr.r has no equitable r-coloring.Chen et al.[2]proposed the following strengthening of Theorem I and Brooks'theorem. Conjecture 2 (Chen et al.[2]).IfG is an r-colorable graph with A(G)<r.then either G has an equitable r-coloring or (G)zr+1 or r=2 and G contains an odd cycle or r is odd and G contains Krr Using Brooks'theorem this is equivalent to: Conjecture 3(Chen et al.[2).IfGis an r-colorable graph with A(G)<r.then either G has an equitable r-coloring or r is odd and G contains Krr. Some partial cases of Conjecture 3 were proved in [2.10.13.14.9].In particular. Chen et al.[2]proved that the conjecture holds forr=3. The aim of this article is twofold:(1)Prove that Conjecture 3 holds for all graphs deree at most four and (foundaion for further Conjecture 3 by deriving some general properties of hypothetical minimum counter- examples to it as well as properties of optimal colorings of such counter-examples. Journal of Graph Theory DOI 10.2 JOURNAL OF GRAPH THEORY the hypothetical minimum counter-examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r ≤4. Keywords: equitable coloring; maximum degree 1. INTRODUCTION In some applications of graph coloring, such as the mutual exclusion scheduling problem, scheduling in communication systems, construction timetables, and round￾a-clock scheduling (see [1, 11, 12]), there is an additional requirement that color classes be not too large or be of approximately the same size. A model imposing such require￾ment is equitable coloring—a proper coloring such that color classes differ in size by at most one. One of the basic results on equitable coloring is the following theorem by Hajnal and Szemeredi [3]. For a shorter proof see [4] or [8]; for an algorithm see [7]. ´ Theorem 1. For every positive integer r, each graph with (G)≤r has an equitable (r+1)-coloring. This theorem has interesting applications in extremal combinatorial and proba￾bilistic problems. It is natural to ask which graphs G with (G)=r≥3 have equitable r-colorings. Certainly, such graphs are r-colorable and so do not contain the complete graph Kr+1. Note that if r is odd, then the complete bipartite graph Kr,r has no equitable r-coloring. Chen et al. [2] proposed the following strengthening of Theorem 1 and Brooks’ theorem. Conjecture 2 (Chen et al. [2]). If G is an r-colorable graph with (G)≤r, then either G has an equitable r-coloring or (G)≥r+1 or r=2 and G contains an odd cycle or r is odd and G contains Kr,r. Using Brooks’ theorem this is equivalent to: Conjecture 3 (Chen et al. [2]). If G is an r-colorable graph with (G)≤r, then either G has an equitable r-coloring or r is odd and G contains Kr,r. Some partial cases of Conjecture 3 were proved in [2, 10, 13, 14, 9]. In particular, Chen et al. [2] proved that the conjecture holds for r=3. Theorem 4 (Chen et al. [2]). Let G be a connected graph with (G)≤3. Then G has no equitable 3-coloring if and only if G=K4 or G=K3,3. The aim of this article is twofold: (1) Prove that Conjecture 3 holds for all graphs with maximum degree at most four and (2) build a foundation for further progress on Conjecture 3 by deriving some general properties of hypothetical minimum counter￾examples to it as well as properties of optimal colorings of such counter-examples. Journal of Graph Theory DOI 10.1002/jgt 2011 Wiley Periodicals, Inc. J Graph Theory 71: 31--48, 2012 32 JOURNAL OF GRAPH THEORY