Note on Perfect Forests in Digraphs. / Gutin, Gregory; Yeo, Anders.

In: Journal of Graph Theory, Vol. 85, No. 2, 17.06.2016, p. 372-377.

Research output: Contribution to journalArticlepeer-review

E-pub ahead of print




A spanning subgraph F of a graph G is called perfect if F is a forest, the degree inline image of each vertex x in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP-hard, for the three others this problem is polynomial-time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.
Original languageEnglish
Pages (from-to)372-377
Number of pages6
JournalJournal of Graph Theory
Issue number2
Early online date17 Jun 2016
Publication statusE-pub ahead of print - 17 Jun 2016
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26469674