A dichotomy for tame graph classes defined by small forbidden induced subgraphs

Given a graph G, a minimal separator in G is a subset of vertices that separates some non-adjacent vertex pair a, b and is inclusion-minimal with respect to this property (separation of a and b). Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-time solvable for classes of graphs with a polynomially bounded number of minimal separators. Graph classes having polynomially bounded number of minimal separators are called tame. Several well-known graph classes are tame, including chordal graphs, permutation graphs, circular-arc graphs, and circle graphs. We perform a systematic study of the question which classes of graphs defined by small forbidden induced subgraphs are tame. We focus on sets of forbidden induced subgraphs with at most four vertices and obtain a complete dichotomy.

Joint work with Martin Milanič.