Distance-hereditary graphs are clique-perfect

DOI10.1016/j.dam.2005.07.011zbMath1110.68108OpenAlexW1995194793MaRDI QIDQ2489948

Maw-Shang Chang, Chuan-Min Lee

Publication date: 28 April 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.07.011

zbMATH Keywords

GraphsDistance-hereditary graphsClique-independence numberClique-transversal number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

The algorithmic complexity of the minus clique-transversal problem ⋮ The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths ⋮ Clique-transversal number of graphs whose clique-graphs are trees ⋮ Clique-perfectness and balancedness of some graph classes ⋮ On some graph classes related to perfect graphs: a survey ⋮ Unique response Roman domination: complexity and algorithms ⋮ Weighted maximum-clique transversal sets of graphs ⋮ On the complexity of variations of mixed domination on graphs^† ⋮ Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ Bounds on the clique-transversal number of regular graphs ⋮ Clique-perfectness of claw-free planar graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Signed and minus clique-transversal functions on graphs ⋮ Clique-perfectness of complements of line graphs ⋮ Signed clique-transversal functions in graphs ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ Clique-perfectness of complements of line graphs ⋮ Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs ⋮ The clique-perfectness and clique-coloring of outer-planar graphs ⋮ Approximation algorithms for clique transversals on some graph classes

Cites Work

• Unnamed Item
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• Clique-transversal sets of line graphs and complements of line graphs
• Completely separable graphs
• Neighborhood perfect graphs
• Distance-hereditary graphs
• Chains, antichains, and fibres
• Covering all cliques of a graph
• Covering the cliques of a graph with vertices
• On the clique-transversal number of chordal graphs
• On clique-transversals and clique-independent sets
• On covering all cliques of a chordal graph
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• Graph Classes: A Survey
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: Distance-hereditary graphs are clique-perfect