# Disjoint spanning in- and out-arborescences

From Egres Open

Does there exist a value *k* so that in every *k*-arc-connected directed graph *D=(V,A)* and for every node [math]v\in V[/math], there is a spanning in-arborescence and a disjoint spanning out-arborescence rooted in *v*?

## Remarks

This was conjectured by Thomassen^{[1]}. It is not true for *k=2*, open for *k=3*, and it is known that deciding if a digraph contains a spanning in-arborescence and a disjoint spanning out-arborescence rooted at *v* is NP-complete ^{[2]}. A stronger version of this conjecture is the following:
Disjoint strongly connected spanning subgraphs.

## References

- ↑ C. Thomassen,
*Configurations in Graphs of Large Minimum Degree, Connectivity, or Chromatic Number*, Annals of the New York Academy of Sciences 555, Combinatorial Mathematics: Proceedings of the Third International Conference (2006), 402-412. DOI link. - ↑ J. Bang-Jensen, G. Gutin,
*Digraphs: Theory, Algorithms and Applications*, 2nd. ed., Springer Verlag (2009), Section 9.6. Google Books link.