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 this page instead for the normal view: No antitwins in minimal imperfect graphs |
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
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