Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Matthew Johnson

Dabrowski, K.K., Johnson, M., Paesani, G. , Paulusma, D. & Zamaraev, V. (2019), Independent transversals versus transversals, 88: EuroComb 2019. Bratislava, Slovakia, Comenius University Press, 585-591.

Author(s) from Durham

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.