Slightly triangulated graphs are perfect

DOI10.1007/BF02986675MaRDI QIDQ1340126zbMATH OpenFDO

Authors Frédéric Maire

Publication date 9 February 1995

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02986675

zbMATH Keywords

chordless cyclechordless pathperfect graphsslightly triangulated graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

A graph \(G\) is said to be slightly triangulated iff \(G\) has the following two properties: (i) \(G\) contains no chordless cycle with at least 5 vertices, and (ii) for every induced subgraph \(H\) of \(G\), there is a vertex in \(H\) the neighbourhood of which in \(H\) contains no chordless path of 4 vertices. The author shows that every slightly triangulated graph is perfect. Comparisons with other classes of perfect graphs and open problems are considered too.

Recommendations

• scientific article; zbMATH DE number 969165
• Weakly triangulated graphs
• Slender graphs
• Cycle-perfect graphs are perfect
• New classes of perfect graphs

Cites work

• A characterization of intersection graphs of the maximal rectangles of a polyomino
• scientific article; zbMATH DE number 3885919 (Why is no real title available?)
• scientific article; zbMATH DE number 3885937 (Why is no real title available?)
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 3904622 (Why is no real title available?)
• On a property of the class of n-colorable graphs
• Optimizing weakly triangulated graphs
• Perfect zero–one matrices
• Short-chorded and perfect graphs
• Topics on perfect graphs
• Weakly triangulated graphs

Cited in

(8)

• Slender graphs
• On slim graphs, even pairs, and star-cutsets
• On chordal and perfect plane triangulations
• Classes of perfect graphs
• Wing-triangulated graphs are perfect
• scientific article; zbMATH DE number 969165 (Why is no real title available?)
• More characterizations of triangulated graphs
• Weakly triangulated graphs

This page was built for publication: Slightly triangulated graphs are perfect

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