Extended Path Partition Conjecture for Semicomplete and Acyclic Compositions

Let $D$ be a digraph and let $\lambda (D)$ denote the number of vertices in a longest path of $D$. For a pair of vertex-disjoint induced subdigraphs $A$ and $B$ of $D$, we say that $(A,B)$ is a partition of $D$ if $V(A)\cup V(B)=V(D)\mathrm{.}$ The Path Partition Conjecture (PPC) states that for every digraph, $D$, and every integer $q$ with $1\le q\le \lambda (D)-1$, there exists a partition $(A,B)$ of $D$ such that $\lambda (A)\le q$ and $\lambda (B)\le \lambda (D)-q\mathrm{.}$ Let $T$ be a digraph with vertex set $\{u_1,\dots ,u_t\}$ and for every $i\in [t]$,let$H_i$beadigraphwithvertexset${u_{i,j_i}\colon, j_i\in [n_i]}$\mathrm{.}The\text{em}composition$Q=T[H_1,\dots , H_t]$of$T$and$H_1,\ldots, H_t$isadigraphwithvertexset${u_{i,j_i}\colon, i\in [t], j_i\in [n_i]}$andarcset$$A(Q)=\cup^t_{i=1}A(H_i)\cup {u_{i,j_i}u_{p,q_p}\colon, u_iu_p\in A(T), j_i\in [n_i], q_p\in [n_p]}.$$ We say that $Q$ is acyclic {(semicomplete, respectively)} if $T$ is acyclic {(semicomplete, respectively)}. In this paper, we introduce a conjecture stronger than PPC using a property first studied by Bang-Jensen, Nielsen and Yeo (2006) and show that the stronger conjecture holds for wide families of acyclic and semicomplete compositions.