Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

DOI10.1016/j.endm.2008.01.010zbMath1341.05091OpenAlexW2179401580MaRDI QIDQ5900083

Flavia Bonomo-Braberman, Francisco J. Soulignac, Gabriel Sueiro, Guillermo Durán

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

perfect graphstriangle-free graphsclique-perfect graphscoordinated graphspaw-free graphs\(\{\text{gem}, W_{4}, \text{bull}\}\)-free graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items (1)

NP-hardness of the recognition of coordinated graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-hardness of the recognition of coordinated graphs
• The strong perfect graph theorem
• Partial characterizations of coordinated graphs: Line graphs and complements of forests
• Neighborhood perfect graphs
• Bull-free Berge graphs are perfect
• Paw-free graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On clique-transversals and clique-independent sets
• Recognizing bull-free perfect graphs
• Triangle-free graphs with large chromatic numbers
• Algorithmic aspects of clique-transversal and clique-independent sets
• Recognizing Berge graphs

This page was built for publication: Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs