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

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)\).