K.K. Dabrowski
Independent transversals versus transversals
Dabrowski, K.K.; Johnson, M.; Paesani, G.; Paulusma, D.; Zamaraev, V.
Authors
Professor Matthew matthew.johnson2@durham.ac.uk
Head Of Department
G. Paesani
Professor Daniel daniel.paulusma@durham.ac.uk
Professor
V. Zamaraev
Abstract
We compare the minimum size of a vertex cover, feedback vertex set and odd cycle transversal of a graph with the minimum size of the corresponding variants in which the transversal must be an independent set. We investigate for which graphs H the two sizes are equal whenever the graph in question belongs to the class of H-free graphs. We find complete classifications for vertex cover and almost complete classifications for feedback vertex set and odd cycle transversal.
Citation
Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). Independent transversals versus transversals.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | EuroComb 2019 |
Acceptance Date | May 7, 2019 |
Online Publication Date | Jul 29, 2019 |
Publication Date | Jul 29, 2019 |
Deposit Date | Jun 12, 2019 |
Publicly Available Date | Jun 13, 2019 |
Volume | 88 |
Pages | 585-591 |
Series Number | 3 |
Series ISSN | 0862-9544 |
Public URL | https://durham-repository.worktribe.com/output/1142008 |
Publisher URL | http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1289 |
Files
Accepted Conference Proceeding
(350 Kb)
PDF
You might also like
Temporal vertex cover with a sliding time window
(2018)
Presentation / Conference Contribution
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2018)
Presentation / Conference Contribution
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2024)
Journal Article
Linear read-once and related Boolean functions
(2018)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
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