Sandwiches Missing Two Ingredients of Order Four

Abstract

For a set $\mathcal{F}$ of graphs, an instance of the $\mathcal{F}$-{\sc free Sandwich Problem} is a pair $(G_1,G_2)$ consisting of two graphs $G_1$ and $G_2$ with the same vertex set such that $G_1$ is a subgraph of $G_2$, and the task is to determine an $\mathcal{F}$-free graph $G$ containing $G_1$ and contained in $G_2$, or to decide that such a graph does not exist. Initially motivated by the graph sandwich problem for trivially perfect graphs, which are the $\{P_4,C_4\}$-free graphs, we study the complexity of the $\mathcal{F}$-{\sc free Sandwich Problem} for sets $\mathcal{F}$ containing two non-isomorphic graphs of order four. We show that if $\mathcal{F}$ is one of the sets $\left\{\mathrm{diamond},K_4\right\}$, $\left\{\mathrm{diamond},C_4\right\}$, $\left\{\mathrm{diamond},\mathrm{paw}\right\}$, $\left\{K_4,\overline{K_4}\right\}$, $\left\{P_4,C_4\right\}$, $\left\{P_4,\overline{\mathrm{claw}}\right\}$, $\left\{P_4,\overline{\mathrm{paw}}\right\}$, $\left\{P_4,\overline{\mathrm{diamond}}\right\}$, $\left\{\mathrm{paw},C_4\right\}$, $\left\{\mathrm{paw},\mathrm{claw}\right\}$, $\left\{\mathrm{paw},\overline{\mathrm{claw}}\right\}$, $\left\{\mathrm{paw},\overline{\mathrm{paw}}\right\}$, $\left\{C_4,\overline{C_4}\right\}$, $\left\{\mathrm{claw},\overline{\mathrm{claw}}\right\}$, and $\left\{\mathrm{claw},\overline{C_4}\right\}$, then the $\mathcal{F}$-{\sc free Sandwich Problem} can be solved in polynomial time, and, if $\mathcal{F}$ is one of the sets $\left\{C_4,K_4\right\}$, $\left\{\mathrm{paw},K_4\right\}$, $\left\{\mathrm{paw},\overline{K_4}\right\}$, $\left\{\mathrm{paw},\overline{C_4}\right\}$, $\left\{\mathrm{diamond},\overline{C_4}\right\}$, $\left\{\mathrm{paw},\overline{\mathrm{diamond}}\right\}$, and $\left\{\mathrm{diamond},\overline{\mathrm{diamond}}\right\}$, then the decision version of the $\mathcal{F}$-{\sc free Sandwich Problem} is NP-complete.