G-2002-11
P5-Free Augmenting Graphs and the Maximum Stable Set Problem
Michael U. Gerber, Alain Hertz et David Schindl
The complexity status of the maximum stable set problem in the class of P5-free graphs is unknown. In this paper, we first propose a characterization of all connected P5-free augmenting graphs. We then use this characterization to detect families of subclasses of P5-free graphs where the maximum stable set problem has a polynomial time solution. These families extend several previously studied classes.
Paru en février 2002 , 14 pages