K.K. Dabrowski
Independent transversals versus transversals
Dabrowski, K.K.; Johnson, M.; Paesani, G.; Paulusma, D.; Zamaraev, V.
Authors
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
G. Paesani
Professor Daniel Paulusma 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.
Conference Name | EuroComb 2019 |
---|---|
Conference Location | Bratislava, Slovakia |
Acceptance Date | May 7, 2019 |
Online Publication Date | Jul 29, 2019 |
Publication Date | Jul 29, 2019 |
Deposit Date | Jun 12, 2019 |
Publicly Available Date | Mar 28, 2024 |
Volume | 88 |
Pages | 585-591 |
Series Number | 3 |
Series ISSN | 0862-9544 |
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
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
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