On minimal prime extensions of a four-vertex graph in a prime graph

DOI10.1016/j.disc.2004.06.019zbMath1056.05111OpenAlexW2058537654MaRDI QIDQ704276

Chính T. Hoàng, Jean-Marie Vanherpe, Andreas Brandstädt

Publication date: 13 January 2005

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

Full work available at URL: https://doi.org/10.1016/j.disc.2004.06.019

zbMATH Keywords

Extensions of a four-vertex subgraph in a prime graphModular decompositionModules in graphsPrime graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

All minimal prime extensions of hereditary classes of graphs ⋮ Substitution-closed pattern classes ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ The set of prime extensions of a graph: the finite and the infinite case

Cites Work

• Unnamed Item
• Unnamed Item
• On the closure of triangle-free graphs under substitution
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• On diameters and radii of bridged graphs
• On maximal independent sets of vertices in claw-free graphs
• Stability number of bull- and chair-free graphs revisited
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Extension of hereditary classes with substitutions
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Some classes of perfectly orderable graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH