When All Minimal \(k\)-vertex Separators Induce Complete or Edgeless Subgraphs

Define \(\mathcal{D}_k\) to be the class of graphs such that, for every independent set \(\{v_1,\ldots,v_h\}\) of vertices with \(2 \leq h \leq k\), if \(S\) is an inclusion-minimal set of vertices whose deletion would put \(v_1,\ldots,v_h\) into \(h\) distinct connected components, then \(S\) induces a complete subgraph; also, let \(\mathcal{D} = \bigcap_{k\geq2} \mathcal{D}_k\). Similarly, define \(\mathcal{D}_k’\) and \(\mathcal{D}’\) with “complete” replaced by “edgeless,” and define \(\mathcal{D}_k^*\) and \(\mathcal{D}^*\) with “complete” replaced by “complete or edgeless.” The class \(\mathcal{D}_2\) is the class of chordal graphs, and the classes \(\mathcal{D}\), \(\mathcal{D}_2’\), and \(\mathcal{D}_2^*\) have also been characterized recently. The present paper gives unified characterizations of all of the classes \(\mathcal{D}_k\), \(\mathcal{D}_k’\), \(\mathcal{D}_k^*\), \(\mathcal{D}\), \(\mathcal{D}’\), and \(\mathcal{D}^*\).