✦ LIBER ✦

Partitioning by Monochromatic Trees

✍ Scribed by P.E. Haxell; Y. Kohayakawa

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 192 KB
Volume: 68
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0065

No coin nor oath required. For personal study only.

✦ Synopsis

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 states that r&1 trees suffice for all n.

📜 SIMILAR VOLUMES

Partitioning complete multipartite graph

Partitioning complete multipartite graphs by monochromatic trees

✍ Atsushi Kaneko; M. Kano; Kazuhiro Suzuki 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

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 c

Monochromatic Trees with Respect to Edge

Monochromatic Trees with Respect to Edge Partitions

✍ V. Rodl; B. Voigt 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 270 KB

It is shown. that for every infinite cardinal \(\kappa\) there exists a graph \(F\) on \(\kappa\) vertices satisfying \(F \rightarrow(T)_{i}^{\text {edgen }}\) for every tree \(T\) on \(\kappa\) vertices and all \(i\) satisfying cf \(\kappa \rightarrow((1))_{j}^{3}\). ' 1993 Acadenic Press, Inc.

Partitioning infinite trees

✍ Peter Horak; Katherine Heinrich 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB

Vertex Partitions by Connected Monochrom

Vertex Partitions by Connected Monochromatic k-Regular Graphs

✍ Gábor N. Sárközy; Stanley M. Selkow 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 135 KB

Partitioning of biweighted trees

✍ Alessandro Agnetis; Pitu B. Mirchandani; Andrea Pacifici 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

Monochromatic cycle partitions of edge-c

Monochromatic cycle partitions of edge-colored graphs

✍ Gábor N. Sárközy 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB 👁 1 views

In this article we study the monochromatic cycle partition problem for non-complete graphs. We consider graphs with a given independence number (G) = . Generalizing a classical conjecture of Erd" os, Gyárfás and Pyber, we conjecture that if we r-color the edges of a graph G with (G) = , then the ver