The price of connectivity for cycle transversals

DOI10.1016/j.ejc.2016.06.003zbMath1343.05157OpenAlexW2470675019MaRDI QIDQ739064

Matthew Johnson, Daniël Paulusma, Martin Milanič, Tatiana Romina Hartinger

Publication date: 16 August 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2016.06.003

zbMATH Keywords

\(\mathcal{F}\)-transversal of a graphconnected \(H\)-free graphs

Mathematics Subject Classification ID

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

Related Items (9)

Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ 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 ⋮ 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 ⋮ The price of connectivity for feedback vertex set ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ On cycle transversals and their connected variants in the absence of a small linear forest

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The price of connectivity for dominating set: upper bounds and complexity
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• FPT algorithms for connected feedback vertex set
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Node-weighted Steiner tree approximation in unit disk graphs
• The strong perfect graph theorem
• Connected vertex covers in dense graphs
• Characterizations of strongly chordal graphs
• Dominating cliques in \(P_ 5\)-free graphs
• On approximability of the independent/connected edge dominating set problems
• Parameterized measure \& conquer for problems with no small kernels
• Connecting face hitting sets in planar graphs
• Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
• The Price of Connectivity for Cycle Transversals
• Vulnerability bounds on the number of spanning tree leaves
• On Hadwiger's Number and the Stability Number
• Graph Classes: A Survey
• 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 cycle transversals