Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width

DOI10.1016/j.dam.2004.01.014zbMath1084.05056OpenAlexW2040593601MaRDI QIDQ1764808

Raffaele Mosca, Andreas Brandstädt, Hoàng-Oanh Le

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.01.014

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items (24)

A local characterization of bounded clique-width for line graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Colouring diamond-free graphs ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ Bounding clique-width via perfect graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Recent developments on graphs of bounded clique-width ⋮ On distance-3 matchings and induced matchings ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ On algorithms for (\(P_5\), gem)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Distance-hereditary graphs
• Complement reducible graphs
• Modular decomposition and transitive orientation
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The Complexity of the Partial Order Dimension Problem
• A Linear Recognition Algorithm for Cographs
• A characterization of ptolemaic graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• The Pathwidth and Treewidth of Cographs
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width