Independent transversals versus transversals

MaRDI QIDQ6621186FDOQ6621186

Authors: Konrad Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Victor Zamaraev 

Publication date: 18 October 2024

Published in: Acta Mathematica Universitatis Comenianae. New Series (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 7378380
• On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
• On cycle transversals and their connected variants in the absence of a small linear forest
• On cycle transversals and their connected variants in the absence of a small linear forest
• Independent feedback vertex set for \(P_5\)-free graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The NP-Completeness of Edge-Coloring
• Connected feedback vertex set in planar graphs
• The price of connectivity for dominating set: upper bounds and complexity
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• The price of connectivity for vertex cover
• Connected vertex covers in dense graphs
• The price of connectivity for feedback vertex set
• A note on an induced subgraph characterization of domination perfect graphs
• The price of connectivity for cycle transversals
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• Title not available (Why is that?)
• Independent feedback vertex set for \(P_5\)-free graphs
• Connected vertex cover for \((sP_1+P_5)\)-free graphs

Cited In (2)

• On blockers and transversals of maximum independent sets in co-comparability graphs
• On the price of independence for vertex cover, feedback vertex set and odd cycle transversal

This page was built for publication: Independent transversals versus transversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6621186)