Independent transversals versus transversals
Main Article Content
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.
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 http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1289/698
Issue
Section
EUROCOMB 2019