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
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)
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)