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