| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652446 | Electronic Notes in Discrete Mathematics | 2009 | 6 Pages |
Abstract
We show that P4-tidy graphs have a linear number of minimal separators and present an algorithm to list them in linear time, extending an algorithm for P4-sparse graphs given by Nikolopoulos and Palios. We also give bounds on the number and total size of all minimal separators of P4-tidy and P4-lite graphs. Moreover, we show that these bounds are tight for such classes of graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
