BNY property conjecture for digraphs

Let DD be a digraph. A kk-path subdigraph of DD is a collection of kk vertex-disjoint paths, and let λk(D)\lambda_k(D) denote the maximum order of a kk-path subdigraph; in particular, λ(D)=λ1(D)\lambda(D)=\lambda_1(D). A digraph DD satisfies the BNY property if, for every integer qq with 1qλ(D)11\leq q\leq\lambda(D)-1, there is a partition (A,B)(A,B) of DD such that λ(A)q\lambda(A)\leq q and, for all k{1,2,,V(B)}k\in\{1,2,\dots,|V(B)|\}, λk(B)λk(D)q\lambda_k(B)\leq\lambda_k(D)-q. BNY property conjecture. Property BNY holds for every digraph. The BNY property is a strengthening of the Path Partition Conjecture, and the paper proves it for wide families of acyclic and semicomplete compositions; the assertion for arbitrary digraphs remains open.

Sources & referencesView supporting material

Primary source

Jiangdong Ai, Stefanie Gerke, Gregory Gutin and Yacong Zhou, “Extended Path Partition Conjecture for Semicomplete and Acyclic Compositions”, arXiv:2111.09633 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.