Some Further Researches On The Equitable Coloring Of Graphs

All graphs considered in this paper are finite, simple and undirected graphs. For a graph G, we use V(G),(?)G(?), E(G),(?)E(?), A(G),△(G), g(G), d(G) andF(G) to denote the vertex set, the order, the edge set, the size, the maximum(vertex) degree,the minimum(vertex) degree, the girth, the diameter and the face set of G. Sometimes, we denote△(G),δ(G), g(G), d(G) as△,δ, g and d in simple.A k-vertex coloring of G is an assignment of k colors,1,2,...,k,to the vertices of G. The coloring is proper if no two distinct adjacent vertices have the same color. G is k-vertex-colorable if G has a proper k-vertex coloring. The chromatic number, x(G) of G is the minimum k for which G is k-colorable. If x(G)=k, G is said to be k-chromatic.If G has a proper k-vertex coloring and its color classes differ by at most one, the G is said to be equitably colored with k colors. The smallest integer n for which G can be equitably colored with n colors is called the equitable chromatic number Xe(G).There are a lot of conclusions in the area of equitable coloring. One of the famous conclusion is proved by Hajnal and Szemeredi that for any integer r, if△(G)≤r, then G has an (k+1)-equitable coloring. Recent researches focus on the next two conjectures.Conjecture 1:For any connected graph G, except the complete graph, the odd cycle and the complete bipartite graph K2m+1,2m+1,△(G)=△,xe(G)≤△(G).Conjecture 2:Let r≥3. If G is a graph satisfying d(x)+d(y)≤2r for every edge xy, and G has no equitable r-coloring, then G contains either Kr+1 or Km.2r-m for some odd m.In this paper, the next theorem is proved which is a special instance of conjecture 2.Theorem 2.1:Let r≥3 and G be a graph such that there is only one pair of vertex vavh∈E(G), the sum d(va)+d(vb)= 2r, and the sum of other pair of vertices are smaller than 2r, then G has an equitable coloring with r colors. A (t, k, d)tree coloring of G is an assignment of k colors,1,2,...,k, to the vertices of G, that is, the vertices of G are partitioned into k classes V1, V2,..., Vk, such that for each Vi (1≤i≤k), every component of G[Vi] is a tree of diameter at most k and maximum degree at most d. The smallest integer t for which G is (t, k, d)-tree colorable is called the (k,d)-tree chromatic number, denoted by Xk,d(G).If G has a (t, k,d)-tree coloring and its color classes differ by at most one, then G is said to be equitably (t, k, d)-tree colored. The equitable (k, d)-tree chromatic number, denoted by xk,d＝(G), is the smallest integer t for which G has a equitable (t, k, d)-tree coloring.Given an integer t, if for any t'≤t, there is an equitable(t',k,d)-tree coloring, we call G can be fully equitable (t,k,d)-tree colorable. The fully equitable (k, d)-tree chromatic number, denoted by xk,d≡(G), is the smallest integer t for which G has a fully equitable (t, k, d)-tree coloring. If k=+∞, d=+∞, the (equitable, fully equitable) (t,k,d)-tree coloring is also called to be (equitable, fully equitable, respectively) t-tree coloring. The (equitable, fully equitable) vertex arboricity is the smallest integer t for which G has a (equitable, fully equitable, respectively) t-tree coloring, denoted by va(G)(va=(G), va≡(G), respectively).In Chapter 3 of this paper, we get the following theorems:Theorem 3.1 Let G be a planner graph and the girth g(G)≤5. Then va≡(G)≤3.Theorem 3.2 Let G be a planner graph and the girth g(G)≤6. Then va≡(G)≤2, moreover, va≡(G)= 1 if and only if G is a forest.