Partitioning Complete Multipartite Graphs by Monochromatic Trees

The tree partition number of an r-edge-colored graph G, denoted by tr(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex-disjoint monochromatic trees. We determine t2(K(n1,n2,...,nk)) of the complete k-partite graph K(n1,n2,...,nk). In particular, we prove that t2(K(n, m)) = ⌊(m − 2)/2 n ⌋ + 2, where 1 ≤ n ≤ m.