Stable sets in certain \(P_6\)-free graphs
type: Item
instance of: scholarly article
title: Stable sets in certain \(P_6\)-free graphs
zbMATH Open document ID: 0929.05076
DOI: 10.1016/S0166-218X(99)00046-3
author: Raffaele Mosca
published in: Discrete Applied Mathematics
publication date: 2000-01-11T00:00:00Z
review text: The maximum independent set problem for graphs is NP-complete in general and for some restricted classes such as \((C_3,C_4)\)-free graphs. For other classes polynomial time algorithms exist, examples are the \(P_4\)-free graphs. The complexity status is not known for \(P_5\)-free graphs. The author presents \(O(n^{4.5})\) algorithms for \((P_6,C_3)\)-free graphs and (\(P_6\), paw)-free graphs and an \(O(n^4)\) algorithm for \((P_6,C_4)\)-free graphs. The paper contains some misprints. For example, \(N_{N(z)}(z)\) should be replaced by \(N_{N(z)}(Z)\).
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1339916
zbMATH Keywords: stable set
zbMATH Keywords: independent set
zbMATH Keywords: \(P_6\)-free graph
zbMATH Keywords: triangle-free graph
zbMATH Keywords: square-free graph
zbMATH Keywords: paw-free graph
MaRDI profile type: Publication
cites work: Dominating cliques in \(P_ 5\)-free graphs
cites work: A characterization of graphs without long induced paths
cites work: Stability number of bull- and chair-free graphs
cites work: A Graph-Theoretic Approach to a Class of Integer-Programming Problems
cites work: On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Some simplified NP-complete graph problems
cites work: The complexity of comparability graph recognition and coloring
cites work: Q3221420
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
cites work: Paw-free graphs
cites work: Q4770411
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
description: scientific article; zbMATH DE number 1339916