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: Hamiltonian subcubic graphs, chordal graphs, and distance-hereditary graphs. In Hamiltonian subcubic graphs we show that deciding matching-decyclability is NP-complete even if there are exactly two vertices of degree two. For chordal and distance-hereditary graphs, we present characterizations of matching-decyclability that lead to $O(n)$-time recognition algorithms.

Source : oai:arXiv.org:1707.02473

DOI : 10.23638/DMTCS-20-2-15

Volume: vol. 20 no. 2

Section: Graph Theory

Published on: November 20, 2018

Submitted on: October 19, 2017

Keywords: Computer Science - Discrete Mathematics