Independent transversals versus transversals

Main Article Content

Konrad K. Dabrowski Matthew Johnson Giacomo Paesani Daniël Paulusma Viktor Zamaraev


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.

Article Details

How to Cite
Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). Independent transversals versus transversals. Acta Mathematica Universitatis Comenianae, 88(3), 585-591. Retrieved from