Weighted parameters in (P₅, P₅)-free graphs

DOI10.1016/S0166-218X(97)00093-0MaRDI QIDQ1382285zbMATH OpenOpenAlexFDO

Authors Vassilis Giakoumakis, Irena Rusu

Publication date 5 January 1999

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

algorithmsmodular decompositionperfect graphsweighted colouringweighted cliqueweighted transversal

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• scientific article; zbMATH DE number 3893237
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures

Cites work

• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 6472575 (Why is no real title available?)
• A Fast Algorithm for the Decomposition of Graphs and Posets
• A charming class of perfectly orderable graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• The edge inducibility of graphs

Cited in

(24)

• On -sparse graphs and other families
• Graphs with No Induced Five‐Vertex Path or Antipath
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Complexity results for equistable graphs and related classes
• On the complexity of 4-coloring graphs without long induced paths
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• On the stable set problem in special \(P_{5}\)-free graphs
• Stability number in subclasses of \(P_5\)-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On algorithms for (P₅, gem)-free graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• The stable set polytope for some extensions of \(P_4\)-free graphs
• Independent domination in finitely defined classes of graphs
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Algorithmic aspects of a general modular decomposition theory
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• More results on weighted independent domination
• On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
• Stability number of bull- and chair-free graphs revisited
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs

This page was built for publication: Weighted parameters in \((P_5,\overline {P_5})\)-free graphs

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