ON EXTENDED P-4-REDUCIBLE AND EXTENDED P-4-SPARSE GRAPHS

A graph G was defined in [16] as P-4-reducible, if no vertex in G belo ngs to more than one chordless path on four vertices or P-4. A graph G is defined in [15] as P-4-sparse if no set of five vertices induces m ore than one P-4 in G. P-4-sparse graphs generalize both P-4-reducible and the well known class of P-4-free graphs or cographs. In an extend ed abstract in [11] the first author introduced a method using the mod ular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of P-4- sparse and extended P-4-sparse graphs. In this paper, we begin by pres enting the complete information about the method used in [11]. We prop ose a unique tree representation of P-4-sparse and a unique tree repre sentation of P-4-reducible graphs leading to a simple linear recogniti on algorithm for both classes of graphs. In this way we simplify and u nify the solutions for these problems, presented in [16-19]. The tree representation of an n-vertex P-4-sparse or a P-4-reducible graph is t he key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are NP- complete on general graphs. Finally, by relaxing the restriction conce rning the exclusion of the C-5 cycles from P-4-sparse and P-4-reducibl e graphs, we introduce the class of the extended P-4-sparse and the cl ass of the extended P-4-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithm s to these new classes of graphs.