Every 4-Colorable Graph with Maximum Degree 4 Has an Equitable 4-Coloring H.A.Kierstead1 and A.V.Kostochka2.3 1DEPARTMENT OF MATHEMATICS AND STATISTICS ARIZONA STATE UNIVERSITY TEMPE ARIZONA 85287 E-mail:kierstead@asu.edu 2DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS,URBANA ILLINOIS 61801 INSTITUTE OF MATHEMATICS NOVOSIBIRSK,RUSSIA E-mail:kostochk@math.uiuc.edu Received August 3,2009:Revised May 21.2011 Published online 25 August 2011 in Wiley Online Library (wileyonlinelibrary.com). D0I10.1002jgt.20630 Abstract:Chen et al.,conjectured that for r=3,the only connected graphs with maximum degree at most r that are not equitably r-colorable are K.r(for odd r)and K+1.If true,this would be a joint strengthening of the Hajnal-Szemeredi theorem and Brooks'theorem.Chen et al.,proved that their conjecture holds for r=3.In this article we study properties of Contract grant sponsor:NSA and NSF;Contract grant numbers:MDA 904-03- 1-0007:DMS-0901520(to H.A.K);Contract grant Journal of Graph Theory 2011 Wiley Periodicals,Inc. 37 Every 4-Colorable Graph with Maximum Degree 4 Has an Equitable 4-Coloring H. A. Kierstead1 and A. V. Kostochka2,3 1DEPARTMENT OF MATHEMATICS AND STATISTICS ARIZONA STATE UNIVERSITY, TEMPE ARIZONA 85287 E-mail: kierstead@asu.edu 2DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS, URBANA ILLINOIS 61801 3INSTITUTE OF MATHEMATICS NOVOSIBIRSK, RUSSIA E-mail: kostochk@math.uiuc.edu Received August 3, 2009; Revised May 21, 2011 DOI 10.1002/jgt.20630 Abstract: Chen et al., conjectured that for r ≥3, the only connected graphs with maximum degree at most r that are not equitably r-colorable are Kr,r (for odd r) and Kr+1. If true, this would be a joint strengthening of the Hajnal–Szemeredi theorem and Brooks’ theorem. Chen et al., proved ´ that their conjecture holds for r =3. In this article we study properties of Contract grant sponsor: NSA and NSF; Contract grant numbers: MDA 904-03- 1-0007; DMS-0901520 (to H. A. K); Contract grant sponsor: NSF and Russian Foundation for Basic Research; Contract grant numbers: DMS-0650784; 09-01- 00244-a (to A. V. K). Journal of Graph Theory 2011 Wiley Periodicals, Inc. 1 Published online in Wiley Online Library (wileyonlinelibrary.com). 25 August 2011 31