Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs

DOI10.1016/j.dam.2007.05.048zbMath1138.05030OpenAlexW2168694080MaRDI QIDQ2482103

Maria Chudnovsky, Guillermo Durán, Flavia Bonomo-Braberman

Publication date: 16 April 2008

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

Full work available at URL: http://hdl.handle.net/10533/139402

zbMATH Keywords

perfect graphsclaw-free graphsline graphsclique-perfect graphshereditary clique-Helly graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Perfect graphs (05C17)

Related Items (12)

NP-hardness of the recognition of coordinated graphs ⋮ Clique-perfectness and balancedness of some graph classes ⋮ On some graph classes related to perfect graphs: a survey ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ Clique-perfectness of claw-free planar graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Claw-free cubic graphs with clique-transversal number half of their order ⋮ Clique-perfectness of complements of line graphs ⋮ Partial characterizations of coordinated graphs: Line graphs and complements of forests ⋮ Clique-perfectness of complements of line graphs ⋮ The clique-perfectness and clique-coloring of outer-planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Kernels in perfect line-graphs
• Claw-free graphs. III: Circular interval graphs
• Claw-free graphs. IV: Decomposition theorem
• Neighborhood perfect graphs
• Bull-free Berge graphs are perfect
• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• A description of claw-free perfect graphs
• Decomposition of balanced matrices
• On clique-transversals and clique-independent sets
• Algorithmic aspects of clique-transversal and clique-independent sets
• Recognizing Berge graphs
• Über iterierte Clique-Graphen
• On balanced graphs
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Algorithmic Aspects of Vertex Elimination on Graphs
• Line perfect graphs
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs