The price of connectivity for feedback vertex set

Belmonte, R.; Hof, van 't P.; Kaminski, M.; Paulusma, D.

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

Citation

Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2013, December). The price of connectivity for feedback vertex set. Presented at 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013, Pisa, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013
• Publication Date: Jan 1, 2013
• Deposit Date: Dec 20, 2014
• Publisher: Scuola Normale Superiore
• Pages: 123-128
• Series Title: Publications of the Scuola Normale Superiore
• Series Number: 16
• Book Title: The seventh European conference on combinatorics, graph theory and applications.
• ISBN: 9788876424748
• DOI: https://doi.org/10.1007/978-88-7642-475-5_20
• Public URL: https://durham-repository.worktribe.com/output/1154651