摘要
A heterochromatie tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by tr （G）, is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most tr（Kn） vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of Kn.
A heterochromatie tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by tr （G）, is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most tr（Kn） vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of Kn.
基金
Supported by the National Natural Science Foundation of China (No.11071130 and 11101378)
Zhejiang Innovation Project (Grant No.T200905)
Zhejiang Provifenincial Natural Science Foundation of China(Z6090150)
