Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem (Q2656894)

Summary: A graph class is said to be tame if graphs in the class have a polynomially bounded number of minimal separators. Tame graph classes have good algorithmic properties, which follow, for example, from an algorithmic metatheorem of \textit{F. V. Fomin} et al. [SIAM J. Comput. 44, No. 1, 54--87 (2015; Zbl 1357.05144)]. We show that a hereditary graph class \(\mathcal{G}\) is tame if and only if the subclass consisting of graphs in \(\mathcal{G}\) without clique cutsets is tame. This result and Ramsey's theorem lead to several types of sufficient conditions for a graph class to be tame. In particular, we show that any hereditary class of graphs of bounded clique cover number that excludes some complete prism is tame, where a complete prism is the Cartesian product of a complete graph with a \(K_2\). We apply these results, combined with constructions of graphs with exponentially many minimal separators, to develop a dichotomy theorem separating tame from non-tame graph classes within the family of graph classes defined by sets of forbidden induced subgraphs with at most four vertices.