## The price of connectivity for feedback vertex set

*Rémy Belmonte, Pim van 't Hof, Marcin Kamiński and Daniël Paulusma*

This paper appeared in the proceedings of Eurocomb 2013, the 7th European Conference on Combinatorics, Graph Theory and Applications (held on September 9-13, 2013 in Pisa, Italy), *CRM Series*, vol. 16, pp. 123-128, 2013.

[__DOI__][__Preprint__]

### Abstract:

Let fvs(*G*) and cfvs(*G*) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph *G*, respectively. In general graphs, the ratio cfvs(*G*)/fvs(*G*) can be arbitrarily large. We study the interdependence between fvs(*G*) and cfvs(*G*) in graph classes defined by excluding one induced subgraph *H*. We show that the ratio cfvs(*G*)/fvs(*G*) is bounded by a constant for every connected *H*-free graph *G* if and only if *H* is a linear forest. We also determine exactly those graphs *H* for which there exists a constant *c _{H}* such that cfvs(

*G*) ≤ fvs(

*G*) +

*c*for every connected

_{H}*H*-free graph

*G*, as well as exactly those graphs

*H*for which we can take

*c*= 0.

_{H}