Note on Perfect forests in Digraphs

Gregory Gutin, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review


A spanning subgraph F of a graph G is called perfect if F is a forest, the degree dF(X) 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
JournalJournal of Graph Theory
Issue number2
Pages (from-to)372-377
Publication statusPublished - 2017
Externally publishedYes


  • degree parity
  • digraphs
  • directed forests
  • perfect forests


Dive into the research topics of 'Note on Perfect forests in Digraphs'. Together they form a unique fingerprint.

Cite this