Independent transversals versus transversals

MaRDI QIDQ6621186zbMATH OpenFDO

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)

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)

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₅-free graphs

Cites work

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

Cited in

(2)

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

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)