Strong branchwidth and local transversals (Q1764812)

From MaRDI portal
Revision as of 18:40, 7 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Strong branchwidth and local transversals
scientific article

    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