Disjoint spanning in- and out-arborescences
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?
This was conjectured by Thomassen. 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 . A stronger version of this conjecture is the following: Disjoint strongly connected spanning subgraphs.
- 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.