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.
Categories: math.CO cs.DM