The Problem Of Partitioning Of Graphs By Heterochromatic Trees

An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. An edge-colored graph G is called monochromatic if all the edges of it have the same color. An edge-colored graph G is called heterochromatic if any two edges (if it has) of it have different colors.From Erdos's remark, every 2-edge-coloring of Kn contains a monochromatic spanning tree. As one of variants of Erdos's remark, an natural problem is to partition an r-edge-colored Kn into as few as possible vertex disjoint monochromatic trees. Erdos et al. introduced the monochromatic subgraph partition number of an r-edge-colored graph. Analogous to the monochromatic tree partition number, Chen et al. introduced the heterochromatic tree partition number of an r-edge-colored graph G. These parti-tion problems inspired many researchers'interests because of its importance in graph theory.The thesis considers the problem of partitioning graphs by heterochromatic trees. The main results obtained in this dissertation can be summarized as follows:In the first part, we present a polynomial time algorithm which finds at most tr(Km,n) vertex disjoint heterochromatic trees to cover all the vertices of a given r-edge-colored graph Km,n.Based on the previous works, we consider the complete tripartite graphs and give a explicit expression of the heterochromatic tree partition number for complete tripartite graphs in the second part.