Independent transversals versus transversals



Dabrowski, KK, Johnson, M, Paesani, G, Paulusma, D and Zamaraev, V ORCID: 0000-0001-5755-4141
(2019) Independent transversals versus transversals. .

[img] Text
paper44.pdf - Accepted Version

Download (350kB) | Preview

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: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 01 Jul 2020 09:15
Last Modified: 03 Apr 2021 11:01
URI: https://livrepository.liverpool.ac.uk/id/eprint/3092259