Disjoint spanning in- and out-arborescences

From Egres Open
Jump to: navigation, search

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

  1. ↑ 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.
  2. ↑ J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd. ed., Springer Verlag (2009), Section 9.6. Google Books link.
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Disjoint_spanning_in-_and_out-arborescences&oldid=603"