Skip to main content

Research Repository

Advanced Search

Independent transversals versus transversals

Dabrowski, K.K.; Johnson, M.; Paesani, G.; Paulusma, D.; Zamaraev, V.

Independent transversals versus transversals Thumbnail


Authors

K.K. Dabrowski

G. Paesani

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 Jun 13, 2019
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







You might also like



Downloadable Citations