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 cliqueweighted colouringweighted transversal

Mathematics Subject Classification ID

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

Review text

Let \(G\) be a graph with \(n\) vertices and \(m\) edges. The authors give \(O(n(m+n))\) algorithms for finding a maximum weighted clique and an approximate weighted colouring in a \((P_5, \overline {P_5})\)-free graph. They also obtain an \(O(m+n)\) algorithm for finding a minimum weighted transversal of the \(C_5\) in a \((P_5, \overline {P_5})\)-free graph.

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

• A charming class of perfectly orderable graphs
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• 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?)
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• The edge inducibility of graphs

Cited in

(25)

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