Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
A graph $G$ is {\em matching-decyclable} if it has a matching $M$ such that $G-M$ is acyclic. Deciding whether $G$ is matching-decyclable is an NP-complete problem even if $G$ is 2-connected, planar, and subcubic. In this work we present results on matching-decyclability in the following classes: Ha...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-11-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3998/pdf |