The independence-number-two conjecture for prescribed roots

Let D=(V,A)D=(V,A) be a digraph, and let calpha(D)calpha(D) denote its independence number. An out-branching rooted at ss is denoted by Bs+B_s^+, and an in-branching rooted at tt is denoted by BtB_t^-. The branchings are arc-disjoint if they have no common arcs. A digraph is 33-arc-strong if its arc-connectivity is at least 33.

Prescribed-roots conjecture. Every 33-arc-strong digraph D=(V,A)D=(V,A) with calpha(D)=2calpha(D)=2 has a pair of arc-disjoint branchings Bs+,BtB_s^+,B_t^- for every choice of s,t\roVs,t\ro V.

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

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.