Stable sets in certain P₆-free graphs

DOI10.1016/S0166-218X(99)00046-3MaRDI QIDQ1304476zbMATH OpenFDO

Authors Raffaele Mosca

Publication date 11 January 2000

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

zbMATH Keywords

independent settriangle-free graphstable set\(P_6\)-free graphsquare-free graphpaw-free graph

Mathematics Subject Classification ID

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

Recommendations

• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• On maximum independent sets in \(P_{5}\)-free graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Some results on stable sets for \(k\)-colorable \(P_{6}\)-free graphs and generalizations
• Independent set in \(P_5\)-free graphs in polynomial time

Cites work

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

Cited in

(26)

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

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

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