Back

G-2002-11

P5-Free Augmenting Graphs and the Maximum Stable Set Problem

, , and

BibTeX reference

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.

, 14 pages

Research Axis