Strong branchwidth and local transversals (Q1764812)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Strong branchwidth and local transversals |
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
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
0.764532744884491
0 references
0.7600722312927246
0 references
0.7576638460159302
0 references
0.7529119253158569
0 references
0.7495443820953369
0 references