## 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.

Original language | English |
---|---|

Journal | Journal of Graph Theory |

Volume | 85 |

Issue number | 2 |

Pages (from-to) | 372-377 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - 2017 |

Externally published | Yes |

## Keywords

- degree parity
- digraphs
- directed forests
- perfect forests