EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 33 The structure of the article is the following.In the next section we prove that minimum counter-examples to Conjecture 3 do not contain certain dense subgraphs.In Sections 3 and 4 we define nearly equitable and optimal nearly equitable colorings of minimum counter-examples to Conjecture 3 and derive some properties of such colorings.In of of The n4.In Section 5 we digress from the main ine todiscuss the following question.If a graph with max imum degree r contains K.it still may have an equitable r-coloring:an example is the graph that consists of two disjoint copies of Krr.Suppose that Conjecture 3 holds for all graphs with maximum degree r and at most sr+I vertices and that H is an (sr+1)-vertex equitably r-colorable graph with maximum degree at most r.The question that we discuss is:Under these conditions.for how many verticesyV(H)could the graph H- y have uitable coloring?The answe is 4 and w use this result to pro e propertie optimal nearly equitable e colorings of min 3.the erive som properties that yield 3 c o C e for all graphs with maximum degree 4. Most of our notation is standard.For example,by A(G).o(G).and y(G)we denote the maximum degree,the clique number,and the chromatic number of a graph G. respectively.All graphs are simple.If S is a set of edges whose ends are in V(G). the n G+S denotes the gnotaionincg on V(G)with edge set E(G)US.Possible deviations fr following. ra graph G.we let G: =IV(G)I.IIGII E(G)I.For a vertex y and set of vertices X.Nx(y):=N(y)nX and dx(y):=INx(y)l.The set of edges of G linking vertices in A to vertices in B is denoted by EG(A,B)or simply by E(A,B).For a set S and element x,we write S+x for Su(x)and S-x for S\[x). For a function f:V-Z.the restriction of f to WcV is denoted by flW.For a positive integer n,the set (1.....n)is denoted by [n]. 2.FORBIDDEN SUBGRAPHS Suppose that Conjecture 3 fails,and let Gbe a counter-example.Then,for some integer r,(G)<r,and if r is odd,then KrG,but G has no equitable r-coloring.We may assume that |Gl is divisible by r,since G will still be a counter-example if we add a disjoint clique of r-(GI mod r)new vertices.Choose r as small as possible;then choose G=(V,E)with |Gl=rs for some integer s with s as small as possible,and subject to this Gll as small as possible.Ther the co jecture holds for H if A(H) also i h△(H nd H lso G does ontain K+l Moreove ontain K:If r is odd this is by hypothesis;if r is even,it is by th minimality of G,since Kr.r.would be a component with an equitable r-coloring.Clearly the conjecture is true for r<2 and for s=1;so r>3 and s22.In the remainder of this section we identify a collection of dense graphs that cannot be contained in our minimum counter-example G. Proposition 5. Gis connected.Furthermore,for all nonempty proper subsets XCV ifX is divisible by r then E(X,V-X)zr. Proof.We shall show that if either staten nt fails,then G has equitable onsider a prope edge cut F:=E(Y1.Y2)with Y2= -Y1.By the mini mality of G there exist equitable r-colorings fi of G[Yil for i=1.2 Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 3 The structure of the article is the following. In the next section we prove that minimum counter-examples to Conjecture 3 do not contain certain dense subgraphs. In Sections 3 and 4 we define nearly equitable and optimal nearly equitable colorings of minimum counter-examples to Conjecture 3 and derive some properties of such colorings. In particular, these properties yield a new proof of Theorem 4. In Section 5 we digress from the main line to discuss the following question. If a graph with maximum degree r contains Kr,r, it still may have an equitable r-coloring; an example is the graph that consists of two disjoint copies of Kr,r. Suppose that Conjecture 3 holds for all graphs with maximum degree r and at most sr+1 vertices and that H is an (sr+1)-vertex equitably r-colorable graph with maximum degree at most r. The question that we discuss is: Under these conditions, for how many vertices y∈V(H) could the graph H−y have no equitable r-coloring? The answer is 4, and we use this result to prove more properties of optimal nearly equitable colorings of minimum counter-examples to Conjecture 3. In the last section we derive some properties that yield Conjecture 3 for all graphs with maximum degree 4. Most of our notation is standard. For example, by (G), (G), and (G) we denote the maximum degree, the clique number, and the chromatic number of a graph G, respectively. All graphs are simple. If S is a set of edges whose ends are in V(G), then G+S denotes the graph on V(G) with edge set E(G)∪S. Possible deviations from standard notation include the following. For a graph G, we let |G|:=|V(G)|, G := |E(G)|. For a vertex y and set of vertices X, NX(y):=N(y)∩X and dX(y):=|NX(y)|. The set of edges of G linking vertices in A to vertices in B is denoted by EG(A,B) or simply by E(A,B). For a set S and element x, we write S+x for S∪{x} and S−x for S\{x}. For a function f :V →Z, the restriction of f to W ⊆V is denoted by f |W. For a positive integer n, the set {1, ...,n} is denoted by [n]. 2. FORBIDDEN SUBGRAPHS Suppose that Conjecture 3 fails, and let G be a counter-example. Then, for some integer r, (G)≤r, and if r is odd, then Kr,rG, but G has no equitable r-coloring. We may assume that |G| is divisible by r, since G will still be a counter-example if we add a disjoint clique of r−(|G| mod r) new vertices. Choose r as small as possible; then choose G=(V,E) with |G|=rs for some integer s with s as small as possible, and subject to this G as small as possible. Then the conjecture holds for H if (H)<r, and also if both (H)=r and |H|≤|G|−r. Also, G does not contain Kr+1. Moreover, G does not contain Kr,r: If r is odd this is by hypothesis; if r is even, it is by the minimality of G, since Kr,r, would be a component with an equitable r-coloring. Clearly the conjecture is true for r≤2 and for s=1; so r≥3 and s≥2. In the remainder of this section we identify a collection of dense graphs that cannot be contained in our minimum counter-example G. Proposition 5. G is connected. Furthermore, for all nonempty proper subsets X⊂V, if |X| is divisible by r then |E(X,V −X)|≥r. Proof. We shall show that if either statement fails, then G has an equitable r-coloring. Consider a proper edge cut F:=E(Y1,Y2) with Y2=V −Y1. By the mini￾mality of G there exist equitable r-colorings fi of G[Yi] for i=1, 2. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 33