Partitioning by monochromatic trees
type: Item
instance of: scholarly article
title: Partitioning by monochromatic trees
zbMATH Open document ID: 0861.05018
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-02-23T00:00:00Z
review text: 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\geq 3r^4r!(1-1/r)^{3(1-r)}\log r\). This comes close to proving, for large \(n\), a conjecture of \textit{P. Erdös}, \textit{A. Gyárfás} and \textit{L. Pyber} [J. Comb. Theory, Ser. B 51, No. 1, 90-95 (1991; Zbl 0766.05062)], which states that \(r-1\) trees suffice for all \(n\).
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 954824
zbMATH Keywords: tree partition number
zbMATH Keywords: cycle partition number
zbMATH Keywords: monochromatic trees
zbMATH Keywords: partition
zbMATH Keywords: trees
author: Penny Haxell
author: Yoshiharu Kohayakawa
MaRDI profile type: Publication
full work available at URL: jctb.1996.0065
OpenAlex ID: W1978665169
DOI: 10.1006/JCTB.1996.0065
description: scientific article; zbMATH DE number 954824