Cookies

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.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(343Kb)
Full text:Publisher-imposed embargo
(VoR) Version of Record
File format - PDF
(335Kb)
Status:Peer-reviewed
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

Export:
Export
Look up in GoogleScholar