Strong branchwidth and local transversals (Q1764812)

From MaRDI portal
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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    chordal graphs
    0 references
    trees
    0 references
    clique number
    0 references
    0 references