R. Belmonte
The price of connectivity for feedback vertex set
Belmonte, R.; Hof, van 't P.; Kaminski, M.; Paulusma, D.
Authors
Contributors
Jaroslav Nešetřil
Editor
Marco Pellegrini
Editor
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). The price of connectivity for feedback vertex set. In J. Nešetřil, & M. Pellegrini (Eds.), The seventh European conference on combinatorics, graph theory and applications (123-128). https://doi.org/10.1007/978-88-7642-475-5_20
Conference Name | 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013 |
---|---|
Conference Location | Pisa, Italy |
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 |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search