P6- and triangle-free graphs revisited: structure and bounded clique-width
P6- and triangle-free graphs revisited: structure and bounded clique-width
The Maximum Weight Stable Set (MWS) Problem is one of the fundamental problems on graphs. It is well-known to be NP-complete for triangle-free graphs, and Mosca has shown that it is solvable in polynomial time when restricted to P6- and triangle-free graphs. We give a complete structure analysis of (nonbipartite) …