Some observations on maximum weight stable sets in certain P5-free graphs
The maximum weight stable set problem (MWS) is the weighted version of the maximum stable set problem (MS), which is NP-hard. The class of P5-free graphs  i.e., graphs with no induced path of five vertices  is the unique minimal class, defined by forbidding a single connected subgraph, for which the computational complexity of MS is an open question. At the same time, it is known that MS can be efficiently solved for (P5,F) ( P 5 , F ) -free graphs, where F is any graph of five vertices different to a C5. In this paper we introduce some observations on P5-free graphs, and apply them to introduce certain subclasses of such graphs for which one can efficiently solve MWS. That extends or improves some known results, and implies  together with other known results  that MWS can be efficiently solved for (P5,F) ( P 5 , F ) -free graphs where F is any graph of five vertices different to a C5.
p5-free graphs maximum weight stable set problem polynomial time algorithm