Note on Perfect Forests in Digraphs. Issue 2 (17th June 2016)

• Record Type: Journal Article
• Authors: Gutin, Gregory; Yeo, Anders
• Is Part Of: Journal of graph theory. Volume 85:Issue 2(2017)
• Page Start: 372
• Page End: 377
• Publication Date: 2016-06-17
• Subjects: digraphs -- perfect forests -- directed forests -- degree parity; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22066
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A spanning subgraph F of a graph G is called perfect if F is a forest, the degree d F ( 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.