Independent Feedback Vertex Set for P_5-free Graphs

DOI10.4230/LIPIcs.ISAAC.2017.16zbMath1457.68122OpenAlexW2808104346MaRDI QIDQ5136232

Marthe Bonamy, Konrad K. Dabrowski, Daniël Paulusma, Matthew Johnson, Carl Feghali

Publication date: 25 November 2020

Full work available at URL: https://hal.archives-ouvertes.fr/hal-02527077

zbMATH Keywords

independent setfeedback vertex set\(H\)-free graphodd cycle transversal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Independent feedback vertex sets for graphs of bounded diameter ⋮ On the computational complexity of the bipartizing matching problem ⋮ Unnamed Item ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Colouring (P_r+P_s)-Free Graphs

Cites Work

• On parameterized independent feedback vertex set
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The complexity of colouring problems on dense graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Cycle transversals in perfect graphs and cographs
• Independent domination in graphs: A survey and recent results
• On line graphs of subcubic triangle-free graphs
• 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
• Choosability of P 5-Free Graphs
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Recognizing Graphs Close to Bipartite Graphs
• Independent Set in P₅-Free Graphs in Polynomial Time

This page was built for publication: Independent Feedback Vertex Set for P_5-free Graphs