A characterization of graphs with (quasi)-polynomial many minimal separators
A class \(F\) is called tame if for every \(n\)-vertex graph \(G\) in \(F\), \(G\) has at most \(n^{O(1)}\) minimal separators, \(F\) is called quasi-tame if for every \(n\)-vertex graph \(G\) in \(F\), \(G\) has at most \(n^{O(polylog(n))}\) minimal separators, and \(F\) is called feral if there exists a constant \(c > 1\) such that for arbitrarily large \(n\), \(F\) contains an \(n\)-vertex graph \(G\) that has at least \(c^n\) minimal separators.
A central structure in the study of tame graph classes is a structure called a \(k\)-creature. It was conjectured by Abrishami et. al. [JCTB, 2022] that graph classes that exclude a \(k\)-creature for some fixed integer \(k\) are tame. It turns out that this conjecture is (just barely) false, and that an additional structure, \(k\)-critters, must be excluded as well. In particular, we will discuss the following new dichotomy theorem:
Let \(F\) be a hereditary (i.e. closed under vertex deletion) and CMSO2-definable class of graphs. Then \(F\) is one of two types:
(i) Quasi-Tame: This occurs if and only if there exists a natural number \(k\) such that \(F\) does not have any graph that contains a \(k\)-creature nor a \(k\)-critter.
(ii) Feral: This occurs if and only if for all natural numbers k, \(F\) contains a graph with either a \(k\)-creature or a \(k\)-critter.
Joint work with Daniel Lokshtanov