Monochromatic and Heterochromatic Subgraphs in Edge-Colored Graphs - A Survey

Nowadays the term monochromatic and heterochromatic (or rainbow, multicolored) subgraphs of an edge-colored graph appeared frequently in literature, and many results on this topic have been obtained. In this paper, we survey results on this subject. We classify the results into the following categories: vertex-partitions by monochromatic subgraphs, such as cycles, paths, trees; vertex partition by some kinds of heterochromatic subgraphs; the computational complexity of these partition problems; some kinds of large monochromatic and heterochromatic subgraphs. We have to point out that there are a lot of results on Ramsey type problem of monochromatic and heterochromatic subgraphs. However, it is not our purpose to include them in this survey because this is slightly different from our topics and also contains too large amount of results to deal with together. There are also some interesting results on vertex-colored graphs, but we do not include them, either. Supported by NSFC, PCSIRT and the “973” program.