Minimal separators in extended P4P4-laden graphs

In this paper, we use the primeval decomposition tree to compute the minimal separators of some graphs and to describe a linear-time algorithm that lists the minimal separators of extended P4P4-laden graphs, extending an algorithm for P4P4-sparse graphs given by Nikolopoulos and Palios [S.D. Nikolopoulos, L. Palios, Minimal separators in P4P4-sparse graphs, Discrete Math. 306 (3) (2006) 381–392]. We also give bounds on the number and total size of all minimal separators of extended P4P4-laden graphs and some of their subclasses, such as P4P4-tidy and P4P4-lite graphs. Moreover, we show that these bounds are tight for all subclasses considered.