The independence-number-two conjecture for prescribed roots
The independence-number-two conjecture for prescribed roots
Let be a digraph, and let denote its independence number. An out-branching rooted at is denoted by , and an in-branching rooted at is denoted by . The branchings are arc-disjoint if they have no common arcs. A digraph is -arc-strong if its arc-connectivity is at least .
Prescribed-roots conjecture. Every -arc-strong digraph with has a pair of arc-disjoint branchings for every choice of .
This strengthens the preceding independence-number-two claim by requiring arbitrary, possibly different, roots and is presented as an open conjecture in the source.
Sources & referencesView supporting material
Primary source
Joergen Bang-Jensen, Stephane Bessy, Frederic Havet and Anders Yeo, “Arc-disjoint in- and out-branchings in digraphs of independence number at most 2”, arXiv:2003.02107 (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.