Structure and stability number of chair-, co-P- and gem-free graphs revisited

DOI10.1016/S0020-0190(02)00487-8MaRDI QIDQ1007592zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Hoàng-Oanh Le, Jean-Marie Vanherpe

Publication date 23 March 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00487-8

zbMATH Keywords

graph algorithmsmodular decompositionprime graphs(chairclique width of graphsco-Pgem)-free graphsmaximum weight stable set

Mathematics Subject Classification ID

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

Recommendations

• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Stability number of bull- and chair-free graphs revisited
• scientific article; zbMATH DE number 5279372
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• On the structure of (\(P_{5}\),\,gem)-free graphs

Cites work

• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 2154974 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Conic reduction of graphs for the stable set problem
• Efficient and practical algorithms for sequential modular decomposition
• Graph Classes: A Survey
• Handle-rewriting hypergraph grammars
• Linear time solvable optimization problems on graphs of bounded clique-width
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Modular decomposition and transitive orientation
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Some classes of perfectly orderable graphs
• Upper bounds to the clique width of graphs

Cited in

(11)

• New applications of clique separator decomposition for the maximum weight stable set problem
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• On the approximability of the maximum induced matching problem
• Stability number of bull- and chair-free graphs revisited
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• On minimal prime extensions of a four-vertex graph in a prime graph
• The structure of graphs with forbidden induced \(C_4\), \(\overline{C}_4\), \(C_5\), \(S_3\), chair and co-chair
• The stable set polytope for some extensions of \(P_4\)-free graphs
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes

This page was built for publication: Structure and stability number of chair-, co-P- and gem-free graphs revisited

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