# Tuesday 11:30 – Peter Gartland

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