Premium
Partitioning complete multipartite graphs by monochromatic trees
Author(s) -
Kaneko Atsushi,
Kano M.,
Suzuki Kazuhiro
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20044
Subject(s) - combinatorics , mathematics , monochromatic color , multipartite , partition (number theory) , vertex (graph theory) , colored , disjoint sets , graph , discrete mathematics , complete graph , physics , quantum entanglement , materials science , quantum mechanics , optics , composite material , quantum
The tree partition number of an r ‐edge‐colored graph G , denoted by t r ( 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 t 2 ( K ( n 1 , n 2 ,…, n k )) of the complete k ‐partite graph K ( n 1 , n 2 ,…, n k ). In particular, we prove that t 2 ( K ( n , m )) = ⌊ ( m ‐2)/2 n ⌋ + 2, where 1 ≤ n ≤ m . © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005