Note on Perfect Forests

DOI10.1002/JGT.21897MaRDI QIDQ3188659zbMATH OpenOpenAlexFDO

Authors G. Gutin

Publication date 12 August 2016

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

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

zbMATH Keywords

forestodd degreesperfect matching

Mathematics Subject Classification ID

Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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$. We provide a short proof of the following theorem of A.D. Scott (Graphs & Combin., 2001): a connected graph $G$ contains a perfect forest if and only if $G$ has an even number of vertices.

Recommendations

• Perfect distance forests
• Note on Perfect Forests in Digraphs
• scientific article; zbMATH DE number 5054164
• Coherent forests
• On the likelihood of forests
• Perfect domination excellent trees
• Perfect forests in graphs and their extensions
• scientific article; zbMATH DE number 7724227
• scientific article; zbMATH DE number 1990721
• Canonical forest

Cites work

• Every tree contains a large induced subgraph with all degrees odd
• scientific article; zbMATH DE number 894703 (Why is no real title available?)
• Large Induced Subgraphs with All Degrees Odd
• On induced subgraphs of trees, with restricted degrees
• On induced subgraphs with all degree odd
• On induced subgraphs with odd degrees

Cited in

(12)

• Induced subgraphs of a tree with constraint degree
• Generalized matchings in forests
• scientific article; zbMATH DE number 1990721 (Why is no real title available?)
• Two short proofs of the Perfect Forest Theorem
• Coherent forests
• Note on Perfect Forests in Digraphs
• Perfect forests in graphs and their extensions
• Amicability of forests
• Maximum odd induced subgraph of a graph concerning its chromatic number
• Vertex partitioning of graphs into odd induced subgraphs
• Graphs whose the maximum size of an odd subgraph equal to \(\lfloor \frac{n}{2} \rfloor \)
• Perfect out-forest problem and directed Steiner cycle packing problem

This page was built for publication: Note on Perfect Forests

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