Independent transversals versus transversals

Autor: Dabrowski, K. K., Johnson, M., Paesani, G., Daniel Paulusma, Zamaraev, V.
Jazyk: angličtina
Rok vydání: 2019
Zdroj: Acta Mathematica Universitatis Comenianae
Scopus-Elsevier
Popis: 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.
Databáze: OpenAIRE