Chordal bipartite graphs of bounded tree- and clique-width
type: Item
instance of: scholarly article
title: Chordal bipartite graphs of bounded tree- and clique-width
zbMATH Open document ID: 1044.05060
author: Vadim Lozin
author: Dieter Rautenbach
published in: Discrete Mathematics
publication date: 2004-08-06T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C78
zbMATH DE Number: 2083728
zbMATH Keywords: chordal bipartite graph
zbMATH Keywords: treewidth
zbMATH Keywords: cliquewidth
zbMATH Keywords: forbidden induced subgraph
MaRDI profile type: Publication
full work available at URL: j.disc.2004.02.008
OpenAlex ID: W2063291872
cites work: Biconvex graphs: Ordering and algorithms
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: Characterizations of totally balanced matrices
cites work: Distance-hereditary graphs
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Q4425939
cites work: Independent domination in finitely defined classes of graphs
cites work: Q5463359
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: Handle-rewriting hypergraph grammars
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
cites work: Upper bounds to the clique width of graphs
cites work: Domination in convex and chordal bipartite graphs
cites work: BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
cites work: Bi-complement reducible graphs
cites work: Perfect Elimination and Chordal Bipartite Graphs
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Difference graphs
cites work: Treewidth of Chordal Bipartite Graphs
cites work: Q4517443
cites work: Q4536388
cites work: Bipartite graphs without a skew star
cites work: On the jump number problem in hereditary classes of bipartite graphs
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
cites work: Alternating cycle-free matchings
cites work: HAMILTONian circuits in chordal bipartite graphs
cites work: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
cites work: Q4352948
cites work: On the size of hereditary classes of graphs
cites work: Nonredundant 1’s in $\Gamma $-Free Matrices
cites work: Bipartite permutation graphs
DOI: 10.1016/J.DISC.2004.02.008
description: scientific article; zbMATH DE number 2083728