LAUSR

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)$$(G1,G2) consisting of two graphs $$G_1$$G1 and $$G_2$$G2 with the same vertex set such that $$G_1$$G1 is a subgraph of $$G_2$$G2, and the task is to determine an $$\mathcal{F}$$F-free graph G containing $$G_1$$G1 and contained in $$G_2$$G2, 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\}$${P4,C4}-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,K4, $$\left\{ \mathrm{diamond},C_4\right\} $$diamond,C4, $$\left\{ \mathrm{diamond},\mathrm{paw}\right\} $$diamond,paw, $$\left\{ K_4,\overline{K_4}\right\} $$K4,K4¯, $$\left\{ P_4,C_4\right\} $$P4,C4, $$\left\{ P_4,\overline{\mathrm{claw}}\right\} $$P4,claw¯, $$\left\{ P_4,\overline{\mathrm{paw}}\right\} $$P4,paw¯, $$\left\{ P_4,\overline{\mathrm{diamond}}\right\} $$P4,diamond¯, $$\left\{ \mathrm{paw},C_4\right\} $$paw,C4, $$\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\} $$C4,C4¯, $$\left\{ \mathrm{claw},\overline{\mathrm{claw}}\right\} $$claw,claw¯, and $$\left\{ \mathrm{claw},\overline{C_4}\right\} $$claw,C4¯, 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\} $$C4,K4, $$\left\{ \mathrm{paw},K_4\right\} $$paw,K4, $$\left\{ \mathrm{paw},\overline{K_4}\right\} $$paw,K4¯, $$\left\{ \mathrm{paw},\overline{C_4}\right\} $$paw,C4¯, $$\left\{ \mathrm{diamond},\overline{C_4}\right\} $$diamond,C4¯, $$\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.