No antitwins in minimal imperfect graphs (Q1107542)

From MaRDI portal





scientific article; zbMATH DE number 4065024
Language Label Description Also known as
English
No antitwins in minimal imperfect graphs
scientific article; zbMATH DE number 4065024

    Statements

    No antitwins in minimal imperfect graphs (English)
    0 references
    0 references
    1988
    0 references
    A graph G is perfect if for every induced subgraph H of G, the chromatic number of H equals the largest number of pairwise adjacent vertices in H. The vertices x and y are twins and antitwins if every vertex distinct from x and y is adjacent either to both of them or to neither of them and to precisely one of them respectively. A graph G is minimal imperfect if G itself is imperfect but every proper induced subgraph of G is perfect. Lovász proved that no minimal imperfect graph has twins. The author proves that no minimal imperfect graph contains antitwins.
    0 references
    twins
    0 references
    antitwins
    0 references
    minimal imperfect graph
    0 references
    0 references

    Identifiers