Longest path partitions in generalizations of tournaments (Q2501556): Difference between revisions

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.