On atomic structure of P5-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 P-5-free graphs, where P-5 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. (C) 2013 Elsevier B.V. All rights reserved.