Sandwiches missing two ingredients of order four

For a set $$\mathcal{F}$$ F of graphs, an instance of the $$\mathcal{F}$$ F -free Sandwich Problem is a pair $$(G_1,G_2)$$ ( G 1 , G 2 ) consisting of two graphs $$G_1$$ G 1 and $$G_2$$ G 2 with the same vertex set such that $$G_1$$ G 1 is a subgraph of $$G_2$$ G 2 , and the task is to determine an $$\mathcal{F}$$ F -free graph G containing $$G_1$$ G 1 and contained in $$G_2$$ 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\}$$ { P 4 , C 4 } -free graphs, we study the complexity of the $$\mathcal{F}$$ F -free Sandwich Problem for sets $$\mathcal{F}$$ F containing two non-isomorphic graphs of order four. We show that if $$\mathcal{F}$$ F is one of the sets $$\left\{ \mathrm{diamond},K_4\right\} $$ diamond , K 4 , $$\left\{ \mathrm{diamond},C_4\right\} $$ diamond , C 4 , $$\left\{ \mathrm{diamond},\mathrm{paw}\right\} $$ diamond , paw , $$\left\{ K_4,\overline{K_4}\right\} $$ K 4 , K 4 ¯ , $$\left\{ P_4,C_4\right\} $$ P 4 , C 4 , $$\left\{ P_4,\overline{\mathrm{claw}}\right\} $$ P 4 , claw ¯ , $$\left\{ P_4,\overline{\mathrm{paw}}\right\} $$ P 4 , paw ¯ , $$\left\{ P_4,\overline{\mathrm{diamond}}\right\} $$ P 4 , diamond ¯ , $$\left\{ \mathrm{paw},C_4\right\} $$ paw , C 4 , $$\left\{ \mathrm{paw},\mathrm{claw}\right\} $$ paw , claw , $$\left\{ \mathrm{paw},\overline{\mathrm{claw}}\right\} $$ paw , claw ¯ , $$\left\{ \mathrm{paw},\overline{\mathrm{paw}}\right\} $$ paw , paw ¯ , $$\left\{ C_4,\overline{C_4}\right\} $$ C 4 , C 4 ¯ , $$\left\{ \mathrm{claw},\overline{\mathrm{claw}}\right\} $$ claw , claw ¯ , and $$\left\{ \mathrm{claw},\overline{C_4}\right\} $$ claw , C 4 ¯ , then the $$\mathcal{F}$$ F -free Sandwich Problem can be solved in polynomial time, and, if $$\mathcal{F}$$ F is one of the sets $$\left\{ C_4,K_4\right\} $$ C 4 , K 4 , $$\left\{ \mathrm{paw},K_4\right\} $$ paw , K 4 , $$\left\{ \mathrm{paw},\overline{K_4}\right\} $$ paw , K 4 ¯ , $$\left\{ \mathrm{paw},\overline{C_4}\right\} $$ paw , C 4 ¯ , $$\left\{ \mathrm{diamond},\overline{C_4}\right\} $$ diamond , C 4 ¯ , $$\left\{ \mathrm{paw},\overline{\mathrm{diamond}}\right\} $$ paw , diamond ¯ , and $$\left\{ \mathrm{diamond},\overline{\mathrm{diamond}}\right\} $$ diamond , diamond ¯ , then the decision version of the $$\mathcal{F}$$ F -free Sandwich Problem is NP-complete.