Independent feedback vertex set for \(P_5\)-free graphs
From MaRDI portal
Publication:1739097
DOI10.1007/s00453-018-0474-xzbMath1422.68105arXiv1707.09402OpenAlexW2964258819MaRDI QIDQ1739097
Matthew Johnson, Marthe Bonamy, Carl Feghali, Konrad K. Dabrowski, Daniël Paulusma
Publication date: 25 April 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.09402
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Unnamed Item ⋮ Partitioning \(P_4\)-tidy graphs into a stable set and a forest ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Faster 3-Coloring of Small-Diameter Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
- On parameterized independent feedback vertex set
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Efficient edge domination in regular graphs
- The complexity of colouring problems on dense graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Dominating cliques in \(P_ 5\)-free graphs
- Efficient edge domination problems in graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
- Independent feedback vertex sets for graphs of bounded diameter
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Vertex colouring and forbidden subgraphs -- a survey
- Cycle transversals in perfect graphs and cographs
- Independent domination in graphs: A survey and recent results
- Faster deterministic \textsc{Feedback Vertex Set}
- On line graphs of subcubic triangle-free graphs
- Boundary classes for graph problems involving non-local properties
- Partition the vertices of a graph into one independent set and one acyclic set
- Finding small separators in linear time via treewidth reduction
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Choosability of P 5-Free Graphs
- The NP-Completeness of Edge-Coloring
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Dominating induced matchings in graphs containing no long claw
- Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
- Reducibility among Combinatorial Problems
- Recognizing Graphs Close to Bipartite Graphs
- Independent Feedback Vertex Set for P_5-free Graphs
- Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
- Independent Set in P5-Free Graphs in Polynomial Time
This page was built for publication: Independent feedback vertex set for \(P_5\)-free graphs
