GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH

DOI10.1142/S0129054104002364zbMATH Open1101.68719MaRDI QIDQ5696971FDOQ5696971

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

Publication date: 19 October 2005

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

Recommendations

• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• On the structure of (\(P_{5}\),\,gem)-free graphs
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Bounding the clique-width of \(H\)-free chordal graphs
• Coloring (gem, co‐gem)‐free graphs

zbMATH Keywords

clique-widthmodules and homogeneous sets in graphsgem- and co-gem-free graphs

Mathematics Subject Classification ID

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

Cites Work

• Graph Classes: A Survey
• 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
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• \(k\)-NLC graphs and polynomial algorithms
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• A characterization of graphs without long induced paths
• Strong tree-cographs are Birkhoff graphs
• On the \(p\)-connectedness of graphs---a survey

Cited In (25)

• Colouring of graphs with Ramsey-type forbidden subgraphs
• Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• Bounding the Clique-Width of H-free Chordal Graphs
• Bounding the Mim-Width of Hereditary Graph Classes.
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Clique-Width for Graph Classes Closed under Complementation
• Title not available (Why is that?)
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Well-quasi-ordering versus clique-width: new results on bigenic classes
• A local characterization of bounded clique-width for line graphs
• Bounding the clique-width of \(H\)-free split graphs
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Bounding clique-width via perfect graphs
• Colouring diamond-free graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Clique‐width: Harnessing the power of atoms
• The stable set polytope for some extensions of \(P_4\)-free graphs
• On minimal prime extensions of a four-vertex graph in a prime graph
• List coloring in the absence of two subgraphs
• Classifying the clique-width of \(H\)-free bipartite graphs
• Bounding Clique-Width via Perfect Graphs
• Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
• Bounding the mim‐width of hereditary graph classes
• Clique-width of graphs defined by one-vertex extensions
• Optimal centrality computations within bounded clique-width graphs

This page was built for publication: GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5696971)