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
Variations on the Gallai-Milgram theorem - MaRDI portal

Variations on the Gallai-Milgram theorem (Q1112833)

From MaRDI portal





scientific article; zbMATH DE number 4079451
Language Label Description Also known as
English
Variations on the Gallai-Milgram theorem
scientific article; zbMATH DE number 4079451

    Statements

    Variations on the Gallai-Milgram theorem (English)
    0 references
    1988
    0 references
    The author strengthens the Gallai-Milgram theorem for digraphs \(D\) with independence number two: ``Let \(x\) be a vertex in \(D\) such that for any vertex \(y\neq x\), there exists a path in \(D\) from \(x\) to \(y\); then \(D\) is spanned by two disjoint paths such that \(x\) is the initial vertex of one of them.'' He proposes various problems and conjectures strengthening the Gallai-Milgram theorem and the Gallai-Roy theorem for strong digraphs.
    0 references
    0 references
    chromatic number
    0 references
    path partition
    0 references
    independence number
    0 references

    Identifiers