Minimal separators in extended $P_4$-laden graphs

We show that extended $P_4$-laden graphs have a linear number of minimal separators and present an algorithm to list them in linear time, extending an algorithm for $P_4$-sparse graphs given by Nikolopoulos and Palios. We also give bounds on the number and total size of all minimal separators of extended $P_4$-laden graphs and some of its subclasses, such as, $P_4$-tidy and $P_4$-lite graphs. Moreover, we show that these bounds are tight for all subclasses considered.

2010