Independent Feedback Vertex Set for P₅-free Graphs

DOI10.4230/LIPICS.ISAAC.2017.16MaRDI QIDQ5136232zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Independent feedback vertex set for P₅-free graphs
• Independent feedback vertex sets for graphs of bounded diameter
• Independent set in P₅-free graphs in polynomial time
• On parameterized independent feedback vertex set
• On parameterized independent feedback vertex set
• On maximum independent sets in \(P_{5}\)-free graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex set on graphs of bounded independent set size
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set

Cites work

• Choosability of P 5-Free Graphs
• Cycle transversals in perfect graphs and cographs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Deterministic Algorithms for the Independent Feedback Vertex Set Problem
• Dominating cliques in \(P_ 5\)-free graphs
• Finding small separators in linear time via treewidth reduction
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Independent domination in graphs: A survey and recent results
• Independent set in P₅-free graphs in polynomial time
• On line graphs of subcubic triangle-free graphs
• On parameterized independent feedback vertex set
• Partition the vertices of a graph into one independent set and one acyclic set
• Recognizing Graphs Close to Bipartite Graphs
• The complexity of colouring problems on dense graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms

Cited in

(7)

• On cycle transversals and their connected variants in the absence of a small linear forest
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Independent feedback vertex set for P₅-free graphs
• On the computational complexity of the bipartizing matching problem
• Independent feedback vertex sets for graphs of bounded diameter
• Colouring (P_r+P_s)-Free Graphs
• scientific article; zbMATH DE number 7378380 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136232)