On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
From MaRDI portal
Publication:6181986
DOI10.1016/j.ejc.2023.103821OpenAlexW2979477659MaRDI QIDQ6181986
Daniël Paulusma, Matthew Johnson, Giacomo Paesani, Konrad K. Dabrowski, 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
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The price of connectivity for dominating set: upper bounds and complexity
- The price of connectivity for feedback vertex set
- A note on an induced subgraph characterization of domination perfect graphs
- On parameterized independent feedback vertex set
- The price of connectivity for cycle transversals
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Connected vertex covers in dense graphs
- Paw-free graphs
- 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
- Independent feedback vertex set for \(P_5\)-free graphs
- On line graphs of subcubic triangle-free graphs
- The NP-Completeness of Edge-Coloring
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- The Price of Connectivity for Vertex Cover
- Connected Feedback Vertex Set in Planar Graphs
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
This page was built for publication: On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
