Dabrowski, K.K. and Johnson, M. and Paesani, G. and Paulusma, D. and Zamaraev, V. (2019) 'Independent transversals versus transversals.', Acta Mathematica Universitatis Comenianae., 88 (3). pp. 585-591.
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.
|Full text:||(AM) Accepted Manuscript|
Download PDF (343Kb)
|Full text:||Publisher-imposed embargo |
(VoR) Version of Record
File format - PDF (335Kb)
|Publisher Web site:||http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1289|
|Date accepted:||07 May 2019|
|Date deposited:||13 June 2019|
|Date of first online publication:||29 July 2019|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|