Rooted non-separating out-branching conjecture

Let DD be a digraph on at least LL vertices. Write λ(D)\lambda(D) for its arc-connectivity and α(D)\alpha(D) for its independence number, and let Bs+B_s^+ denote an out-branching rooted at ss. A non-separating out-branching is an out-branching with the non-separation property studied in the paper. Rooted non-separating out-branching conjecture. There exists an integer LL such that every digraph DD on at least LL vertices with λ(D)2\lambda(D)\geq 2 and α(D)=2\alpha(D)=2 has a non-separating out-branching Bs+B_s^+ for every choice of sVs\in V. The source notes that an infinite class of examples has such a branching from every vertex, but does not resolve the conjecture.

Sources & referencesView supporting material

Primary source

Joergen Bang-Jensen, Stéphane Bessy and Anders Yeo, “Non-separating spanning trees and out-branchings in digraphsof independence number 2”, arXiv:2007.02834 (2020).

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.