Vertex Partition Problem Of Edge-colored Graphs

Vertex partition problem is one of hot topics in graph theory. The topic has important theoretical significants in graph theory and has wide applications in several fields including computer science and information science. From a famous remark of Erdos, we know that every2-edge-coloring of Kn contains a monochro-matic spanning tree. As one of variants of Erdos remark, Bollobas et al. proposed an natural problem is to partition an r-edge-colored Kn into as few as possi-ble vertex disjoint monochromatic trees. In fact, the study of vertex partition problem of edge-colored graphs can be dated back to the70’s or80’s of the last century. Erdos et al. introduced the monochromatic subgraph partition prob-lem of r-edge-colored graph, and the researchers have obtained many results on vertex partitions by monochromatic subgraphs such as cycles, paths, trees. Anal-ogous to the monochromatic tree partition number, Chen et al. introduced the heterochromatic tree partition number of an r-edge-colored graph G.In this thesis, we consider the problem of partitioning graphs by monochro-matic trees and heterochromatic trees.In Chapter1, we give the present the history and development of the monochro-matic and heterochromatic subgraphs partition problems of edge-colored graphs.In Chapter2, we give the monochromatic tree partition number of an r-edge-colored complete multipartite graph under a restricted edge-coloring.In Chapter3, we construct two types of canonical r-edge-colorings of Kn1,n2,…nk. From the constructions, we determine an lower bound of heterochromatic tree par-tition number of Kn1,n2,…,nk.In Chapter4, we determine an upper bound of heterochromatic tree partition number of Kn1,n2,…nk. Moreover, the upper and lower bounds differ by at most one.In Chapter5, we present a conclusion on the problem and consider the algo-rithmic problem of heterochromatic tree partition of Kn1,n2,…,nk.