The price of connectivity for feedback vertex set

DOI10.1016/j.dam.2016.08.011zbMath1358.05156arXiv1510.02639OpenAlexW1938935174MaRDI QIDQ516802

Pim van 't Hof, Daniël Paulusma, Rémy Belmonte, Marcin Kaminski

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.02639

zbMATH Keywords

feedback vertex setforbidden induced subgraphconnected feedback vertex setprice of connectivity

Mathematics Subject Classification ID

Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (7)

Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Connected feedback vertex set on AT-free graphs ⋮ Unnamed Item ⋮ Non-empty intersection of longest paths in \(H\)-free graphs ⋮ Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs ⋮ On cycle transversals and their connected variants in the absence of a small linear forest

Cites Work

• Unnamed Item
• The price of connectivity for dominating set: upper bounds and complexity
• The price of connectivity for cycle transversals
• Connected vertex covers in dense graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Connecting face hitting sets in planar graphs
• Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
• On Hadwiger's Number and the Stability Number
• Perfect connected-dominant graphs
• The Price of Connectivity for Vertex Cover
• Connected Feedback Vertex Set in Planar Graphs

This page was built for publication: The price of connectivity for feedback vertex set