On unavoidability of trees with \(k\) leaves (Q1396655)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On unavoidability of trees with \(k\) leaves
scientific article

    Statements

    On unavoidability of trees with \(k\) leaves (English)
    0 references
    8 July 2003
    0 references
    Let \(g(k)\) denote the least integer such that every oriented tree with \(n\) vertices and \(k\) leaves is contained in every tournament with \(n+g(k)\) vertices. The author and S. Thomassé have conjectured that \(g(k) \leq k-1\); see [Discrete Math. 243, 121-134 (2002; Zbl 0995.05037)]. In the present paper the author proves this conjecture for a certain restricted family of oriented trees that he calls constructible.
    0 references
    0 references
    oriented tree
    0 references
    tournament
    0 references
    0 references
    0 references
    0 references