Chordal bipartite graphs of bounded tree- and clique-width (Q1827785)
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: Chordal bipartite graphs of bounded tree- and clique-width |
scientific article; zbMATH DE number 2083728
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Chordal bipartite graphs of bounded tree- and clique-width |
scientific article; zbMATH DE number 2083728 |
Statements
Chordal bipartite graphs of bounded tree- and clique-width (English)
0 references
6 August 2004
0 references
The treewidth of degree-bounded chordal bipartite graphs is bounded, more precisely, \(\text{ tw}(G) \leq \Delta(G)^2\). Similarly, the cliquewidth of \(k\)-fork-free chordal bipartite graphs is bounded, where a \(k\)-fork is the graph obtained from \(K_{1,k+1}\) by subdividing one edge once. For chordal bipartite graphs in general both parameters are unbounded, see \textit{A. Brandstädt} and \textit{V. V. Lozin} [Ars Comb. 67, 273--281 (2003)].
0 references
chordal bipartite graph
0 references
treewidth
0 references
cliquewidth
0 references
forbidden induced subgraph
0 references
0 references
0 references
