When All Minimal $k$-vertex Separators Induce Complete or Edgeless Subgraphs

Abstract

Define ${\mathcal{D}}_k$ to be the class of graphs such that, for every independent set $\{v_1,\dots ,v_h\}$ of vertices with $2\le h\le k$, if $S$ is an inclusion-minimal set of vertices whose deletion would put $v_1,\dots ,v_h$ into $h$ distinct connected components, then $S$ induces a complete subgraph; also, let $\mathcal{D}=\bigcap _{k\ge 2}{\mathcal{D}}_k$. Similarly, define ${\mathcal{D}}_k^{\prime }$ and ${\mathcal{D}}^{\prime }$ with “complete” replaced by “edgeless,” and define ${\mathcal{D}}_k^{\ast }$ and ${\mathcal{D}}^{\ast }$ 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^{\prime }$, and ${\mathcal{D}}_2^{\ast }$ have also been characterized recently. The present paper gives unified characterizations of all of the classes ${\mathcal{D}}_k$, ${\mathcal{D}}_k^{\prime }$, ${\mathcal{D}}_k^{\ast }$, $\mathcal{D}$, ${\mathcal{D}}^{\prime }$, and ${\mathcal{D}}^{\ast }$.