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.
Independent transversals versus transversals / Dabrowski, K. K.; Johnson, M.; Paesani, G.; Paulusma, D.; Zamaraev, V.. - 88:3(2019), pp. 585-591. ( EuroConference on Combinatorics, Graph Theory and Applications Bratislava, Slovacchia ).
Independent transversals versus transversals
Paesani G.;
2019
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
