Longest path partitions in generalizations of tournaments (Q2501556)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Longest path partitions in generalizations of tournaments
scientific article

    Statements

    Longest path partitions in generalizations of tournaments (English)
    0 references
    0 references
    0 references
    0 references
    14 September 2006
    0 references
    In a digraph \(D\), let \(\lambda (D)\) denote the length of a longest directed path. The path partition conjecture states that for every digraph \(D\) and every choice of positive integers \(\lambda _1\) and \(\lambda _2\) such that \(\lambda (D) = \lambda _1 + \lambda _2\), \(D\) can be partitioned into two digraphs \(D_1\) and \(D_2\) such that \(\lambda (D_i) \leq \lambda _i\) for \(i = 1, 2.\) The authors prove that the conjecture holds for certain generalizations of tournaments. It holds when \(D\) is quasi-transitive, extended semicomplete, or is locally in-semicomplete. It holds with equality when \(D\) is locally in-semicomplete, or extended semicomplete. The results rely on the decomposition of a quasi-transitive digraph into strong or connected components, following a theorem by Bang-Jensen and Huang.
    0 references
    locally in-semicomplete digraph
    0 references
    quasi-transitive digraph
    0 references
    extended semicomplete digraph
    0 references

    Identifiers