Partitioning Complete Graphs by Heterochromatic Trees  

作　　者：Ze-min JIN Xue-liang LI 

机构地区：[1]Department of Mathematics,Zhejiang Normal University [2]Center for Combinatorics and LPMC,Nankai University

出　　处：《Acta Mathematicae Applicatae Sinica》2012年第4期625-630,共6页应用数学学报（英文版）

基　　金：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)

摘　　要：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.

关 键 词：edge-colored graph heterochromatic tree PARTITION 

分 类 号：O157.5[理学—数学] Q243[理学—基础数学]