THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES

DOI10.1142/S0129054108005772zbMath1155.68057OpenAlexW2026563873MaRDI QIDQ3526986

Jordan Volz, Vadim V. Lozin

Publication date: 25 September 2008

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054108005772

zbMATH Keywords

hereditary class

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Bounding clique-width via perfect graphs ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Minimal classes of graphs of unbounded clique-width ⋮ A new graph construction of unbounded clique-width ⋮ Recent developments on graphs of bounded clique-width ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Bi-complement reducible graphs
• Clique-width of partner-limited graphs
• Chordal bipartite graphs of bounded tree- and clique-width
• Bipartite graphs without a skew star
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES