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