Equitable Coloring Of Some Classes Of Graphs

All graphs considered in this paper are finite, simple,and undirected. For a graph G, we use V(G), |G|, E(G), e(G),Δ(G),δ(G) and g(G) to denote the vertex set, order ,edge set, size, maximum degree, minimum degree, and girth,respectively. For a vertex v∈V(G), let N_G(v) denotes the neighbor of vertex v and d_G(v) = |N_G(v)|. If U (?) V(G), G[U] denotes the subgraph of G induced by U. For a vertex u∈V(G), G - u denotes the subgraph of G by deleting the vertex u together with its incident edges. For an edge xy, G - xy denotes the subgraph of G by deleting the edge xy. For U (?) V(G) and W (?) V(G), e(U, W) denotes the number of edges between U and W. e(u, W) denotes e({u},W). The complete bipartite graph with bipartition (X,Y), where |X| = m and |Y| = n, is denoted by K_m,n. Sometimes, we denoteΔ(G),δ(G), g(G), d_G(v), N_G(v) asΔ,δ, g, d(v), N(v) in simple.A proper k-coloring of a graph G is a mappingφfrom V(G) to {1,2,..., k} such thatφ(x)≠φ(y) for every edge xy of G. A proper vertex coloring is equitable if the size of color classes differ by at most one. The equitable chromatic number of G is denoted byχ_e(G). The equitable chromatic threshold of G, denoted byχ_e^*(G), is the smallest integer m such that G is equitably n-colorable for all n≥m. It is obvious thatχ_e(G)≤χ_e^*(G) for any graph G. Hajnal and Szemeredi [2] proved thatχ_e^*(G)≤Δ(G) + 1 for each graph G. This answered a question of Paul Erdos. Meyer [1] proved thatχ^*(T)≤(?) + 1 for any tree T and he made the following conjecture.Conjecture 1 For any connected graph G, except K_m and C_2m+1 for all m≥1,χ_e(G)≤Δ(G).Recently, Chen, Lih and Wu [4] put forth the following conjecture.Conjecture 2 For any connected graph G, except K_m, C_2m+1 andK_2m+1,2m+1 for all m≥1,χ_e^*(G)≤Δ(G) . The conjecture is proved to be true for graphs G satisfyingΔ(G)≥(?) orΔ(G)≤3, bipartite graphs [6] , planar graphs withΔ≥13 [10] and outerplanar graphs [7|. Recently, Wu and Wang [15] discussed the equitable coloring of planar graphs with large girth.In this paper ,we shall prove by using the similar method in [10] that Conjecture 2 is true for planar graphs G (i)ifΔ≥8 and g≥5 ,or (ii)Δ≥5 and g≥12,or (iii)withou 4,5-cycles. And make some disscuss of square graphs and Mycielski graphs about equitable coloring.