Clique cycle-transversals in distance-hereditary graphs
From MaRDI portal
Publication:299045
DOI10.1016/J.DAM.2014.12.007zbMATH Open1339.05084arXiv1302.1402OpenAlexW2011403320MaRDI QIDQ299045FDOQ299045
Authors: Andreas Brandstädt, Simone Esposito, Fábio Protti, Loana T. Nogueira 
Publication date: 22 June 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: A cycle-transversal of a graph G is a subset T of V(G) such that T intersects every cycle of G. A clique cycle-transversal, or cct for short, is a cycle-transversal which is a clique. Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known. We characterize distance-hereditary graphs admitting a cct in terms of forbidden induced subgraphs. This extends similar results for chordal graphs and cographs.
Full work available at URL: https://arxiv.org/abs/1302.1402
Recommendations
- scientific article; zbMATH DE number 6536189
- Distance-hereditary graphs are clique-perfect
- Dominating cliques in distance-hereditary graphs
- Clique-width for hereditary graph classes
- Distance-hereditary graphs
- On Distance-Transitive Graphs
- Clique cycle transversals in graphs with few \(P_{4}\)'s
- On an extension of distance-hereditary graphs
- scientific article; zbMATH DE number 553916
- scientific article; zbMATH DE number 524154
feedback vertex setclique cycle transversalcycle transversaldistance-hereditary graphsforbidden induced subgraph characterization
Cites Work
- Graph Classes: A Survey
- Finding odd cycle transversals.
- Linear time solvable optimization problems on graphs of bounded clique-width
- Title not available (Why is that?)
- Node-and edge-deletion NP-complete problems
- Distance-hereditary graphs
- Partitioning chordal graphs into independent sets and cliques
- Partitions of graphs into one or two independent sets and cliques
- Cycle transversals in perfect graphs and cographs
- Complexity of graph partition problems
- Characterizing –partitionable Cographs
- Cycle transversals in bounded degree graphs
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
Cited In (5)
This page was built for publication: Clique cycle-transversals in distance-hereditary graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299045)
