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
Strong branchwidth and local transversals - MaRDI portal

Strong branchwidth and local transversals (Q1764812)

From MaRDI portal





scientific article; zbMATH DE number 2136948
Language Label Description Also known as
English
Strong branchwidth and local transversals
scientific article; zbMATH DE number 2136948

    Statements

    Strong branchwidth and local transversals (English)
    0 references
    0 references
    22 February 2005
    0 references
    It is well known that a graph is chordal (i.e., contains no induced cycles of length greater than three) if and only if it is the vertex-intersection graph of subtrees of a tree [see, e.g., \textit{F. Gavril}, J. Comb. Theory, Ser. B 16, 47--56 (1974; Zbl 0266.05101)]. In this paper a more restricted version called strong branch representation is introduced and concerns representations of chordal graphs as edge intersection graphs of subtrees in a tree of maximum degree 3. This yields a new invariant called strong branchwidth (sbw). Among others, the author characterizes the chordal graphs whose sbw is smaller than their clique number.
    0 references
    0 references
    chordal graphs
    0 references
    trees
    0 references
    clique number
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references