Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem (Q2656894)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem |
scientific article |
Statements
Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem (English)
0 references
17 March 2021
0 references
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.
0 references
hereditary graph class
0 references
graphs of bounded clique cover number
0 references
0 references