Slightly triangulated graphs are perfect (Q1340126)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Slightly triangulated graphs are perfect
scientific article

    Statements

    Slightly triangulated graphs are perfect (English)
    0 references
    0 references
    9 February 1995
    0 references
    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.
    0 references
    chordless cycle
    0 references
    chordless path
    0 references
    slightly triangulated graph
    0 references
    perfect graphs
    0 references

    Identifiers