Rooted non-separating out-branching conjecture
Rooted non-separating out-branching conjecture
Let be a digraph on at least vertices. Write for its arc-connectivity and for its independence number, and let denote an out-branching rooted at . 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 such that every digraph on at least vertices with and has a non-separating out-branching for every choice of . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.