paper

Decomposition into two trees with orientation constraints

arXiv:1304.3613

Abstract

We prove that deciding whether the edge set of a graph can be partitionned into two spanning trees with orientation constraints is NP-complete. If P NP then this disproves a conjecture of Recski.

5 pages, 2 figures

Decomposition into two trees with orientation constraints · wovepaper