Stable sets in certain \(P_6\)-free graphs

DOI10.1016/S0166-218X(99)00046-3zbMath0929.05076MaRDI QIDQ1304476

Raffaele Mosca

Publication date: 11 January 2000

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

zbMATH Keywords

stable setindependent settriangle-free graph\(P_6\)-free graphsquare-free graphpaw-free graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (23)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Combinatorics and algorithms for augmenting graphs ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ From matchings to independent sets ⋮ A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ On finding augmenting graphs ⋮ Augmenting graphs for independent sets ⋮ Some new hereditary classes where graph coloring remains NP-hard ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Partitioning Graphs into Connected Parts ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Partitioning graphs into connected parts

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Paw-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Dominating cliques in \(P_ 5\)-free graphs
• Stability number of bull- and chair-free graphs
• Some simplified NP-complete graph problems
• The complexity of comparability graph recognition and coloring
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• A characterization of graphs without long induced paths
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Graph-Theoretic Approach to a Class of Integer-Programming Problems

This page was built for publication: Stable sets in certain \(P_6\)-free graphs