Heterochromatic tree partition number of
a complete multipartite graph
He Chen, Zemin Jin, Xueliang Li and Jianhua Tu
Center for Combinatorics and LPMC, Nankai University
Tianjin 300071, P.R. China
Abstract
A heterochromatic 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 k such that whenever the edges of the
graph G are colored with r colors, the vertices of G can be
covered by at most k vertex-disjoint heterochromatic trees. In
this paper we determine the heterochromatic tree partition number
of an r-edge-colored complete multipartite graph Kn1, n2,
..., nk. Though we cannot give explicit expression for the
heterochromatic tree partition number of Kn1, n2,
..., nk, we describe two types of canonical r-edge-colorings
*r, 1 and *r, 2 of Kn1, n2,
..., nk, from which we can obtain the number in polynomial time. As
corollaries, for complete graphs and complete bipartite graphs we
give explicit expression for the heterochromatic tree partition number.
