On slim graphs, even pairs, and star-cutsets

DOI10.1016/0012-365X(92)90134-2MaRDI QIDQ1199476zbMATH OpenFDO

Authors Chính T. Hoàng, Frédéric Maffray

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)90134-2

zbMATH Keywords

parity graphperfect graphslim graphtriangulated graph

Mathematics Subject Classification ID

Graph theory (05C99)

Review text

A Meyniel graph is a perfect graph in which every odd cycle with at least five vertices has at least two chords. A slim graph is any graph obtained from a Meyniel graph by removing all the edges of a given induced subgraph. The authors prove that every slim graph derived from an \(i\)- triangulated graph is a strict quasi-parity graph.

Recommendations

• Slim graphs
• Slender graphs
• Slightly triangulated graphs are perfect
• Even pairs in claw-free perfect graphs
• scientific article; zbMATH DE number 3884201

Cites work

• A new property of critical imperfect graphs and some consequences
• scientific article; zbMATH DE number 3889564 (Why is no real title available?)
• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 3214398 (Why is no real title available?)
• scientific article; zbMATH DE number 3315022 (Why is no real title available?)
• Locally perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On rigid circuit graphs
• On the perfect graph conjecture
• Slim graphs
• Star-cutsets and perfect graphs

Cited in

(6)

• Slender graphs
• Slim graphs
• Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
• Characterisations and Linear-Time Recognition of Probe Cographs
• Slimness of graphs
• On probe permutation graphs

This page was built for publication: On slim graphs, even pairs, and star-cutsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199476)