P4-Reducible Graphs—Class of Uniquely Tree-Representable Graphs

We introduce and characterize a new class of graphs which has a unique tree representation, and which strictly contains the well-known class of cographs. We define three graph operations and show that all the graphs in our class can be constructed from single-vertex graphs by a finite sequence of these operations. Finally, we show that a number of computational problems, including the four classical optimization problems, can be solved efficiently for this new class of graphs.