On the price of independence for vertex cover, feedback vertex set and odd cycle transversal

DOI10.1016/J.EJC.2023.103821MaRDI QIDQ6181986zbMATH OpenOpenAlexFDO

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

Publication date 23 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

price of connectivityprice of independence

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
• Independent transversals versus transversals
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• The price of connectivity for feedback vertex set
• Independent feedback vertex set for \(P_5\)-free graphs

Cites work

• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 7378380 (Why is no real title available?)
• A note on an induced subgraph characterization of domination perfect graphs
• Coloring edges and vertices of graphs without short or long cycles
• Connected feedback vertex set in planar graphs
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• Connected vertex covers in dense graphs
• Independent feedback vertex set for \(P_5\)-free graphs
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• On line graphs of subcubic triangle-free graphs
• On parameterized independent feedback vertex set
• Paw-free graphs
• Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• 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
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Updating the complexity status of coloring graphs without a fixed induced linear forest

Cited in

(1)

• Independent transversals versus transversals

This page was built for publication: On the price of independence for vertex cover, feedback vertex set and odd cycle transversal

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