We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The price of connectivity for feedback vertex set.

Belmonte, R. and Hof, van 't P. and Kaminski, M. and Paulusma, D. (2013) 'The price of connectivity for feedback vertex set.', in The seventh European conference on combinatorics, graph theory and applications. Pisa, Italy: Scuola Normale Superiore, pp. 123-128. Publications of the Scuola Normale Superiore. (16).


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 H for every connected H-free graph G, as well as exactly those graphs H for which we can take c H = 0.

Item Type:Book chapter
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:No date available
Date deposited:16 January 2015
Date of first online publication:2013
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar