Independent transversals versus transversals

Dabrowski, K.K.; Johnson, M.; Paesani, G.; Paulusma, D.; Zamaraev, V.

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.

Citation

Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019, December). Independent transversals versus transversals. Presented at EuroComb 2019, Bratislava, Slovakia

• Presentation Conference Type: Conference Paper (published)
• Conference Name: EuroComb 2019
• Acceptance Date: May 7, 2019
• Online Publication Date: Jul 29, 2019
• Publication Date: Jul 29, 2019
• Deposit Date: Jun 12, 2019
• Publicly Available Date: Jun 13, 2019
• Volume: 88
• Pages: 585-591
• Series Number: 3
• Series ISSN: 0862-9544
• Public URL: https://durham-repository.worktribe.com/output/1142008
• Publisher URL: http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1289