No antitwins in minimal imperfect graphs (Q1107542)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4065024
Language Label Description Also known as
default for all languages
No label defined
    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