{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T09:18:35Z","timestamp":1696670315290},"reference-count":5,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T00:00:00Z","timestamp":1466121600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"Royal Society Wolfson Research Merit Award"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2017,6]]},"abstract":"Abstract<\/jats:title>A spanning subgraph F<\/jats:italic> of a graph G<\/jats:italic> is called perfect<\/jats:italic> if F<\/jats:italic> is a forest, the degree of each vertex x<\/jats:italic> in F<\/jats:italic> is odd, and each tree of F<\/jats:italic> is an induced subgraph of G<\/jats:italic>. Alex Scott (Graphs Combin 17 (2001), 539\u2013553) proved that every connected graph G<\/jats:italic> contains a perfect forest if and only if G<\/jats:italic> 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\u2010hard, for the three others this problem is polynomial\u2010time 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.<\/jats:p>","DOI":"10.1002\/jgt.22066","type":"journal-article","created":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T10:42:54Z","timestamp":1466160174000},"page":"372-377","source":"Crossref","is-referenced-by-count":1,"title":["Note on Perfect Forests in Digraphs"],"prefix":"10.1002","volume":"85","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[{"name":"DEPARTMENT OF COMPUTER SCIENCE, ROYAL HOLLOWAY UNIVERSITY OF LONDON EGHAM SURREY UNITED KINGDOM"}]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[{"name":"ENGINEERING SYSTEMS AND DESIGN SINGAPORE UNIVERSITY OF TECHNOLOGY AND DESIGN SINGAPORE SINGAPORE"},{"name":"DEPARTMENT OF MATHEMATICS UNIVERSITY OF JOHANNESBURG AUCKLAND PARK SOUTH AFRICA"}]}],"member":"311","published-online":{"date-parts":[[2016,6,17]]},"reference":[{"key":"e_1_2_4_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1"},{"key":"e_1_2_4_3_1","unstructured":"Y.Caro Private communication with G. Gutin August2015."},{"key":"e_1_2_4_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21897"},{"key":"e_1_2_4_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730170028"},{"key":"e_1_2_4_6_1","unstructured":"R.SharanandA.Wigderson A new NC algorithm for perfect matching in bipartite cubic graphs 4th Israeli Symposium on Theory of Computing and Systems Jerusalem Israel 1996 pp.202\u2013207."}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.22066","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.22066","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T03:41:04Z","timestamp":1696563664000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,17]]},"references-count":5,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["10.1002\/jgt.22066"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22066","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,17]]}}}