Large-order non-separating out-branching conjecture

Let DD be a digraph on at least KK vertices. Write λ(D)\lambda(D) for its arc-connectivity and α(D)\alpha(D) for its independence number. A non-separating out-branching is an out-branching whose deletion has the non-separation property studied in the paper. Large-order non-separating out-branching conjecture. There exists an integer KK such that every digraph DD on at least KK vertices with λ(D)2\lambda(D)\geq 2 and α(D)=2\alpha(D)=2 has a non-separating out-branching. The conjecture is motivated by a theorem establishing a bound of 1414 vertices; the source gives no resolution of the proposed existence of some universal KK.

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.