Independent Feedback Vertex Set for P₅-free Graphs

DOI10.4230/LIPICS.ISAAC.2017.16zbMATH Open1457.68122OpenAlexW2808104346MaRDI QIDQ5136232FDOQ5136232

Marthe Bonamy, Konrad 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

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

Cites Work

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

Cited In (5)

• Independent feedback vertex set for \(P_5\)-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
• Title not available (Why is that?)

Recommendations

• Subset feedback vertex set on graphs of bounded independent set size 👍 👎
• On Parameterized Independent Feedback Vertex Set 👍 👎
• Independent Set in P₅-Free Graphs in Polynomial Time 👍 👎
• On parameterized independent feedback vertex set 👍 👎
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs 👍 👎
• Independent feedback vertex sets for graphs of bounded diameter 👍 👎
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set 👍 👎
• On maximum independent sets in \(P_{5}\)-free graphs 👍 👎
• Independent feedback vertex set for \(P_5\)-free graphs 👍 👎
• Title not available (Why is that?) 👍 👎

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)