BNY property conjecture for digraphs

About 5 years old · traced to

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 1≤q≤λ(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.

References

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.