Extended path partition conjecture for semicomplete and acyclic compositions
Jiangdong Ai, Stefanie Gerke, Gregory Gutin, Yacong Zhou · Discrete Mathematics · 2022
Let D be a digraph and let λ(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)∪V(B)=V(D). The Path Partition Conjecture (PPC) states that for every digraph, D, and every integer q with 1≤q≤λ(D)−1, there exists a partition (A,B) of D such that λ(A)≤q and λ(B)≤λ(D)−q. Let T be a digraph with vertex set {u1,…,ut} and for every i∈[t], let Hi be a digraph with vertex set {ui,ji:ji∈[ni]}. The composition Q=T[H1,…,Ht] of T and H1,…,Ht is a digraph with vertex set {ui,ji:i∈[t],ji∈[ni]} and arc setA(Q)=∪i=1tA(Hi)∪{ui,jiup,qp:uiup∈A(T),ji∈[ni],qp∈[np]}. 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.