𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partitioning complete multipartite graphs by monochromatic trees

✍ Scribed by Atsushi Kaneko; M. Kano; Kazuhiro Suzuki

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
102 KB
Volume
48
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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)) ¼ b(m À 2)=2 n c þ 2, where 1 n m.

📜 SIMILAR VOLUMES

Partitioning by Monochromatic Trees
Partitioning by Monochromatic Trees
✍ P.E. Haxell; Y. Kohayakawa 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 192 KB

Any r-edge-coloured n-vertex complete graph K n contains at most r monochromatic trees, all of different colours, whose vertex sets partition the vertex set of K n , provided n 3r 4 r! (1&1Âr) 3(1&r) log r. This comes close to proving, for large n, a conjecture of Erdo s, Gya rfa s, and Pyber, which

Special monochromatic trees in two-color
Special monochromatic trees in two-colored complete graphs
✍ Chen, Guantao; Schelp, Richard H.; ?olt�s, ?ubom�r 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB 👁 2 views

For a positive integer k, a set of k + 1 vertices in a graph is a k-cluster if the difference between degrees of any two of its vertices is at most k -1. Given any tree T with at least k 3 edges, we show that for each graph G of sufficiently large order, either G or its complement contains a copy of