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

DOI10.1142/S0129054104002364MaRDI QIDQ5696971zbMATH OpenFDO

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)

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)

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

Cites work

• A Linear Recognition Algorithm for Cographs
• A characterization of graphs without long induced paths
• Complement reducible graphs
• Graph Classes: A Survey
• Handle-rewriting hypergraph grammars
• Linear time solvable optimization problems on graphs of bounded clique-width
• Modular decomposition and transitive orientation
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On the \(p\)-connectedness of graphs---a survey
• On the clique-width of some perfect graph classes
• Some classes of perfectly orderable graphs
• Strong tree-cographs are Birkhoff graphs
• Upper bounds to the clique width of graphs
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• \(k\)-NLC graphs and polynomial algorithms

Cited in

(25)

• Optimal centrality computations within bounded clique-width graphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Clique‐width: Harnessing the power of atoms
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Clique-width of graphs defined by one-vertex extensions
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Classifying the clique-width of \(H\)-free bipartite graphs
• Bounding the clique-width of \(H\)-free chordal graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Colouring diamond-free graphs
• Bounding clique-width via perfect graphs
• Bounding the mim‐width of hereditary graph classes
• A local characterization of bounded clique-width for line graphs
• Well-quasi-ordering versus clique-width: new results on bigenic classes
• Clique-width for graph classes closed under complementation
• List coloring in the absence of two subgraphs
• Well-quasi-ordering versus clique-width: new results on bigenic classes
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Bounding the Mim-Width of Hereditary Graph Classes.
• Bounding clique-width via perfect graphs
• On minimal prime extensions of a four-vertex graph in a prime graph
• scientific article; zbMATH DE number 7204407 (Why is no real title available?)
• The stable set polytope for some extensions of \(P_4\)-free graphs
• Bounding the clique-width of \(H\)-free split 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)