Partitioning by monochromatic trees (Q1125948)

From MaRDI portal





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
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references