Partitioning complete multipartite graphs by monochromatic trees
Partitioning complete multipartite graphs by monochromatic trees
复制标题
DOI：
10.1002/jgt.20044
复制
发表时间：
2005-02
影响因子：
0.9
通讯作者：
A. Kaneko;M. Kano;Kazuhiro Suzuki
中科院分区：
文献类型：
--
作者：
A. Kaneko;M. Kano;Kazuhiro Suzuki
一个r-边着色图G的树划分数记为tr（G），是指当G的边被r种颜色着色时，G的顶点最多可以被k棵顶点不相交的单色树覆盖的最小数k。我们确定完全k部图K（n1，n2，...，nk）的t2（K（n1，n2，...，nk））。特别地，我们证明了t2（K（n，m））=<$（m-2）/2n <$+ 2，其中1 ≤ n ≤ m。© 2004 Wiley Periodicals，Inc. J Graph Theory 48：133-141，2005
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)/2n⌋ + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005