Weakly triangulated graphs (Q801088)

From MaRDI portal





scientific article
Language Label Description Also known as
English
Weakly triangulated graphs
scientific article

    Statements

    Weakly triangulated graphs (English)
    0 references
    0 references
    1985
    0 references
    A graph is triangulated if it has no chordless cycle with four or more vertices. It follows that the complement of a triangulated graph cannot contain a chordless cycle with five or more vertices. We introduce a class of graphs (namely weakly triangulated graphs) which includes both triangulated graphs and complements of triangulated graphs (we define a graph as weakly triangulated if neither it nor its complement contains a chordless cycle with five or more vertices). Our main result is a structural theorem which leads to a proof that weakly triangulated graphs are perfect.
    0 references
    perfect graphs
    0 references
    chordless cycle
    0 references
    triangulated graph
    0 references

    Identifiers