Extended Path Partition Conjecture for Semicomplete and Acyclic Compositions
share
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 {u_1,…, u_t} and for every i∈ [t], let H_i be a digraph with vertex set {u_i,j_i j_i∈ [n_i]}. The composition Q=T[H_1,… , H_t] of T and H_1,…, H_t is a digraph with vertex set {u_i,j_i i∈ [t], j_i∈ [n_i]} and arc set A(Q)=∪^t_i=1A(H_i)∪{u_i,j_iu_p,q_p u_iu_p∈ A(T), j_i∈ [n_i], q_p∈ [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.
READ FULL TEXT