Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs

A vertex set S in a graph G is a minimal separator if there exist vertices u and v that are in distinct connected components of G — S, but in the same connected component of G — S' for every S' ⊂ S. A class F of graphs is called tame if there exists a constant c so that every graph in F on n vertices contains at most O(nc) minimal separators. If there exists a constant c so that every graph in F on n vertices contains at most O(nclog n) minimal separators the class is strongly-quasi-tame. If there exists a constant c > 1 so that F contains n-vertex graphs with at least cn minimal separators for arbitrarily large n then F is called feral. The classification of graph classes into tame or feral has numerous algorithmic consequences, and has recently received considerable attention.