Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
No antitwins in minimal imperfect graphs - MaRDI portal

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