Weighted parameters in \((P_5,\overline {P_5})\)-free graphs

DOI10.1016/S0166-218X(97)00093-0zbMath0903.05045OpenAlexW232959721MaRDI QIDQ1382285

Irena Rusu, Vassilis Giakoumakis

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

algorithmsperfect graphsmodular decompositionweighted colouringweighted cliqueweighted transversal

Mathematics Subject Classification ID

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

Related Items (24)

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

Cites Work

• 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\)
• A Fast Algorithm for the Decomposition of Graphs and Posets
• The edge inducibility of graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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