Independent transversals versus transversals
Independent transversals versus transversals
Summary: 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.
- Durham University United Kingdom
- Sapienza University of Rome Italy
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), price of independence; independent transversal; H-free graphs
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), price of independence; independent transversal; H-free graphs
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!