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 (174Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-88-7642-475-5_20|
|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|