We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Independent transversals versus transversals.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Full text:Publisher-imposed embargo
(VoR) Version of Record
File format - PDF
Publisher Web site:
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