On the structure and stability number of \(P_{5}\)- and co-chair-free graphs

DOI10.1016/S0166-218X(03)00389-5zbMath1029.05142OpenAlexW2076125774MaRDI QIDQ1414581

Raffaele Mosca, Andreas Brandstädt

Publication date: 4 December 2003

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00389-5

zbMATH Keywords

Modular decompositionPrime graphs\(P_5\)- and co-\(P\)-free graphs\(P_5\)- and co-chair-free graphsClique width of graphsMaximum Weight Stable Set Problem on graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (22)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Hereditary unigraphs and Erdős-Gallai equalities ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ On indicated coloring of graphs ⋮ On quasi-monotonous graphs ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques ⋮ Star coloring of certain graph classes ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ On indicated coloring of some classes of graphs ⋮ Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Counting Perfect Matchings and the Switch Chain ⋮ On -sparse graphs and other families

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• On diameters and radii of bridged graphs
• On maximal independent sets of vertices in claw-free graphs
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Modular decomposition and transitive orientation
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• On variations of \(P_{4}\)-sparse graphs
• Stability in \(P_5\)- and banner-free graphs
• On (\(P_{5}\), diamond)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On the vertex packing problem
• Handle-rewriting hypergraph grammars
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• The Complexity of the Partial Order Dimension Problem
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph Classes: A Survey
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: On the structure and stability number of \(P_{5}\)- and co-chair-free graphs