  For a set ${\cal F}$ of graphs, an instance of the ${\cal 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 ${\cal 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 ${\cal F}$-{\sc
free Sandwich Problem} for sets ${\cal F}$ containing two non-isomorphic graphs
of order four. We show that if ${\cal F}$ is one of the sets $\left\{ {\rm
diamond},K_4\right\}$, $\left\{ {\rm diamond},C_4\right\}$, $\left\{ {\rm
diamond},{\rm paw}\right\}$, $\left\{ K_4,\overline{K_4}\right\}$, $\left\{
P_4,C_4\right\}$, $\left\{ P_4,\overline{\rm claw}\right\}$, $\left\{
P_4,\overline{\rm paw}\right\}$, $\left\{ P_4,\overline{\rm diamond}\right\}$,
$\left\{ {\rm paw},C_4\right\}$, $\left\{ {\rm paw},{\rm claw}\right\}$,
$\left\{ {\rm paw},\overline{{\rm claw}}\right\}$, $\left\{ {\rm
paw},\overline{\rm paw}\right\}$, $\left\{ C_4,\overline{C_4}\right\}$,
$\left\{ {\rm claw},\overline{{\rm claw}}\right\}$, and $\left\{ {\rm
claw},\overline{C_4}\right\}$, then the ${\cal F}$-{\sc free Sandwich Problem}
can be solved in polynomial time, and, if ${\cal F}$ is one of the sets
$\left\{ C_4,K_4\right\}$, $\left\{ {\rm paw},K_4\right\}$, $\left\{ {\rm
paw},\overline{K_4}\right\}$, $\left\{ {\rm paw},\overline{C_4}\right\}$,
$\left\{ {\rm diamond},\overline{C_4}\right\}$, $\left\{ {\rm
paw},\overline{\rm diamond}\right\}$, and $\left\{ {\rm diamond},\overline{\rm
diamond}\right\}$, then the decision version of the ${\cal F}$-{\sc free
Sandwich Problem} is NP-complete.
