Cycle transversals in perfect graphs and cographs

DOI10.1016/J.TCS.2012.10.030MaRDI QIDQ1935798zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Synara Brito, Sulamita Klein, Loana T. Nogueira, Fábio Protti

Publication date 19 February 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.10.030

zbMATH Keywords

cographscycle transversalsfeedback vertex setperfect graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Clique cycle-transversals in distance-hereditary graphs
• Clique cycle transversals in graphs with few \(P_{4}\)'s
• On cycle transversals and their connected variants in the absence of a small linear forest
• Cycle transversals in bounded degree graphs
• On clique-transversals and clique-independent sets

Cited in

(20)

• Independent feedback vertex sets for graphs of bounded diameter
• Independent feedback vertex set for P₅-free graphs
• Odd cycle transversal in mixed graphs
• Cycle transversals in bounded degree graphs
• Clique cycle-transversals in distance-hereditary graphs
• Complexity of cycle transverse matching problems
• On equistable, split, CIS, and related classes of graphs
• Corrigendum to ``Cycle transversals in perfect graphs and cographs
• Odd Cycle Transversals and Independent Sets in Fullerene Graphs
• Recognizing Graphs Close to Bipartite Graphs
• Sparse graphs are near-bipartite
• Independent Feedback Vertex Set for P₅-free Graphs
• Cycle transversals in bounded degree graphs
• Clique cycle transversals in graphs with few \(P_{4}\)'s
• Granular computing on basic digraphs
• On cycle transversals and their connected variants in the absence of a small linear forest
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Partitioning P₄-tidy graphs into a stable set and a forest
• Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
• Near-bipartiteness on graphs having small dominating sets

This page was built for publication: Cycle transversals in perfect graphs and cographs

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