Partitioning by monochromatic trees (Q1125948)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Partitioning by monochromatic trees |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partitioning by monochromatic trees |
scientific article |
Statements
Partitioning by monochromatic trees (English)
0 references
23 February 1997
0 references
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\).
0 references
tree partition number
0 references
cycle partition number
0 references
monochromatic trees
0 references
partition
0 references
trees
0 references