Clique cycle-transversals in distance-hereditary graphs
From MaRDI portal
(Redirected from Publication:299045)
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.
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
Cites work
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- Characterizing –partitionable Cographs
- Complexity of graph partition problems
- Cycle transversals in bounded degree graphs
- Cycle transversals in perfect graphs and cographs
- Distance-hereditary graphs
- Finding odd cycle transversals.
- Graph Classes: A Survey
- Linear time solvable optimization problems on graphs of bounded clique-width
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Node-and edge-deletion NP-complete problems
- Partitioning chordal graphs into independent sets and cliques
- Partitions of graphs into one or two independent sets and cliques
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)
