On the structure and stability number of P₅- and co-chair-free graphs

DOI10.1016/S0166-218X(03)00389-5MaRDI QIDQ1414581zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Raffaele Mosca

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

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

Recommendations

• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Stability number in subclasses of \(P_5\)-free graphs
• On the stability number of claw-free \(P_5\)-free and more general graphs
• Stability in \(P_5\)- and banner-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Stability number of bull- and chair-free graphs revisited
• scientific article; zbMATH DE number 1208717
• Vertex-critical \((P_5, \mathrm{chair})\)-free graphs
• 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 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A New Algorithm for Generating All the Maximal Independent Sets
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• A note on \(\alpha\)-redundant vertices in graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Complement reducible graphs
• 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
• Modular decomposition and transitive orientation
• On (\(P_{5}\), diamond)-free graphs
• On diameters and radii of bridged graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On maximal independent sets of vertices in claw-free graphs
• On the clique-width of graph with few \(P_{4}\)'s
• On the vertex packing problem
• On variations of \(P_{4}\)-sparse graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Some classes of perfectly orderable graphs
• Stability in \(P_5\)- and banner-free graphs
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• The Complexity of the Partial Order Dimension Problem
• Upper bounds to the clique width of graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs

Cited in

(28)

• Maximum weight independent sets in hole- and co-chair-free graphs
• On -sparse graphs and other families
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Counting perfect matchings and the switch chain
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Weighted independent sets in classes of \(P_6\)-free graphs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Stability in \(P_5\)- and banner-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• -boundedness and related problems on graphs without long induced paths: a survey
• Maximum weight independent sets in hole- and dart-free graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Coloring (\(P_5\), kite)-free graphs with small cliques
• Star coloring of certain graph classes
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• Hereditary unigraphs and Erdős-Gallai equalities
• On indicated coloring of graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• On minimal prime extensions of a four-vertex graph in a prime graph
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Bounding the clique-width of \(H\)-free chordal graphs
• Stability number of bull- and chair-free graphs revisited
• Independent Sets in Classes Related to Chair-Free Graphs
• On quasi-monotonous graphs

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

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