Preperfect graphs (Q684406)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Preperfect graphs
scientific article

    Statements

    Preperfect graphs (English)
    0 references
    0 references
    0 references
    15 September 1993
    0 references
    A vertex \(x\) is said to be predominant if there exists another vertex \(y\) of \(G\) such that either every maximum clique of \(G\) containing \(y\) contains \(x\) or every maximum stable set containing \(x\) contains \(y\). A graph is then called preperfect if every induced subgraph has a predominant vertex. This paper shows that preperfect graphs are perfect and that several well-known kinds of perfect graphs are preperfect. Meanwhile, it is also shown that a graph \(G\) is perfect iff every induced subgraph \(H\) of \(G\) possesses a minimal absorbant set that meets all maximum cliques of \(H\).
    0 references
    0 references
    predominant
    0 references
    clique
    0 references
    stable set
    0 references
    preperfect graphs
    0 references
    perfect graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references