Equitable Coloring Of Graphs

Graphs considered in this paper are simple, finite, nonempty and undirected. Roughly speaking, the problems that we are concerned in this thesis are mainly as follows:1. Equitable coloring of trees.2. Equitable coloring of complete r-partite graphs.A graph G(V, E) is said to be equitably k-colorable, if the vertices of G are colored with k colors such that no edge joins vertices of the same color and the cardinalities of the color sets differ by at most one, i.e., V(G) can be partitioned into independent sets V1, V2, ..., Vk such that for all i and j, ||Vi| - |Vj|| ≥ 1. The smallest integer k for which G is equitably fc-colorable is called the equitable chromatic number of G, denoted by Xe(G). Obviously, Xe(G) ≤ x(G) ≤ 2, where x(G) is the chromatic number of G. In 1973, VV. Meyer [2] introduced this notion of equitable colorability and proposed a conjecture that Xe(G) ≥ Δ(G) for all connected graphs G except the complete graphs and the odd cycles, where A(G) denotes the maximum degree of G. In fact, in 1970, the work of Hajnal and Szemeredi [18] implied that a graph G is equitably k-colorable if k > Δ(G). Meyer's conjecture has been confirmed for a few special cases such as bipartite graphs [6], outerplanar graphs [8], graphs with Δ(G) ≤1/2|V(G)| or Δ(G) ≥ 3 [4] and planar graphs with Δ(G) ≤ 13 [9]. R.ecently, Meyer's conjecture has also been verified for complete r-partite graphs and line graphs [13], and an explicit formula for the equitable chromatic number of complete r-partite graphs is given [10]. For special classes of graphs the general theorem of Hajnal and Szemeredi can be improved considerably. B. Bollobas and R. K. Guy [5] proved that a tree is equitably 3-colorable if n > 3Δ-8 or n = 3Δ - 10. A. Kostochka [26] proved that every outerplanar graph with maximum degree at most A is equitably k-colorable for every k ≥ A/2 + 1. Sriram V. Pemrnaraju [27] show that any connected outerplanar graph on n vertices with maximum degree at most n/6 is equitably 6-colorable. B. L. Chen and K. VV. Lih [7] proved the following result which determines the set of values k such that a tree is equitably k-colorable.Let tt(G), called the independence number of a graph G, denote the number of vertices in a maximum independent set of G, and G(X,Y) denote the bipartite graph with bipartition (X, Y).Lemma 1.1.[7] Let T = T(X,Y) be a tree such that ||X - Y|| > 1. Then T is equitably k-colorable if and only if k≥ max{3, [(|V(T}| + 1}/(alpha(T- N(v))+2)] }, where v is an arbitrary vertex with d(u) = Δ.Motivated by Lemma 1.1, we obtain other conditions For which a tree T is equitablyk-colorable.Theorem 1.2. Let T be a tree on n vertices with maximum degree A. Then, for k ≥ 3, T is equitably k-colorable if and only if there exists a vertex v of T with d(v) = A such that at(T - N(v)) > [n/k] - 1.Theorem 1.3. Let T = T(X,Y) be a tree with \X = n > m = \Y . Then T is equitably k-colorable if k ≥ [n/(m + 1)] + 1.Theorem 1.4. If T is a tree with maximum degree A, then for any vertex with d(v) = A, T - v is equitably 3-colorable.A tree T is a caterpillar if T ?V is a path which is denoted by Pm = v1v2...vm, where V' = {v 6 V(T) : d(v) = 1}. The path Pni = v1v2...vm is called the spine of the caterpillar. Suppose that d(vi) = di, i = 1, 2, .... m. Also, we may denote this tree by r(d1,:d2:...,dm). LetTheorem 1.5. A caterpillar T(d1,d2, ...,dm) is equitably 2-colorable if and only if a' - b' ≤ 1 for m is even or 0 ≤ a' - b' ≤ 2 for rn is odd.Theorem 1.6. Let T(d1,d2,..., dm) be a caterpillar on n vertices with maximum degree Δ. Then T is equitably k-colorable for k≥ 3 ifΔ aj If a, is odd and aj is even, (ai, aj) is called an odd-even ordered pair. Two ordered pairs, (...