Strong branchwidth and local transversals (Q1764812)

From MaRDI portal





scientific article; zbMATH DE number 2136948
Language Label Description Also known as
default for all languages
No label defined
    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