| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4950882 | Information Processing Letters | 2017 | 4 Pages |
Abstract
As a natural variant of the many decycling notions studied in graphs, we consider the problem to decide whether a given graph G has a matching M such that GâM is a forest. We establish NP-completeness of this problem for 2-connected planar subcubic graphs, and describe polynomial time algorithms that also determine such a matching if it exists for graphs that are claw- and paw-free, P5-free, chordal, and C4-free distance hereditary.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Carlos V.G.C. Lima, Dieter Rautenbach, Uéverton S. Souza, Jayme L. Szwarcfiter,