On atomic structure of P5P5-free subclasses and Maximum Weight Independent Set problem

Graph decompositions play a crucial role in structural graph theory and in designing efficient graph algorithms. Among them, clique separator decomposition (a decomposition tree of the graph whose leaves have no clique separator (so-called atoms)) used by Tarjan for solving various optimization problems recently received much attention. In this note, we first derive the atomic structure of two subclasses of P5P5-free graphs, where P5P5 is a chordless path on five vertices. These results enable us to provide efficient solutions for the Maximum Weight Independent Set problem in these classes of graphs.