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

DOI10.1016/J.EJC.2023.103821OpenAlexW2979477659MaRDI QIDQ6181986FDOQ6181986

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)

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

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

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)

Cites Work

• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• On parameterized independent feedback vertex set
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Connected feedback vertex set in planar graphs
• Paw-free graphs
• The price of connectivity for dominating set: upper bounds and complexity
• Coloring edges and vertices of graphs without short or long cycles
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• 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
• On line graphs of subcubic triangle-free graphs
• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• 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
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration

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)