Note on Perfect Forests in Digraphs

DOI10.1002/JGT.22066MaRDI QIDQ5272922zbMATH OpenOpenAlexFDO

Authors G. Gutin, A. Yeo

Publication date 5 July 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01661

zbMATH Keywords

degree paritydigraphsdirected forestsperfect forests

Mathematics Subject Classification ID

Trees (05C05) Vertex degrees (05C07) Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25)

Abstract: A spanning subgraph $F$ of a graph $G$ is called {em 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., 2001) 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 non-trivial way.

Recommendations

• Perfect forests in graphs and their extensions
• scientific article; zbMATH DE number 7724227
• Tree- and forest-perfect graphs
• A note on perfect graphs
• scientific article; zbMATH DE number 3869356
• Spanning forests of a digraph and their applications
• The forest number in several classes of regular graphs
• Perfect pairs of trees in graphs
• Forests and trees among Gallai graphs
• A note on the arboricity of graphs

Cites work

• Digraphs
• Note on Perfect Forests
• On induced subgraphs with all degree odd

Cited in

(6)

• Degree sum conditions for oriented forests in digraphs
• Generalized matchings in forests
• Note on Perfect Forests
• Two short proofs of the Perfect Forest Theorem
• Perfect forests in graphs and their extensions
• Perfect out-forest problem and directed Steiner cycle packing problem

This page was built for publication: Note on Perfect Forests in Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272922)