Name
Abstract | ||
|---|---|---|
For a set \(\mathcal{F}\) of graphs, an instance of the \(\mathcal{F}\)-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}\)-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}\)-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}\)-free Sandwich Problem is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s10479-019-03174-6 | Annals of Operations Research |
Keywords | Field | DocType |
Graph sandwich problem, Forbidden induced subgraph, Prime graph, Homogeneous set | Discrete mathematics,Graph,Vertex (geometry),Mathematics,Graph sandwich problem | Journal |
Volume | Issue | ISSN |
abs/1704.01922 | 1-2 | 0254-5330 |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José D. Alvarado | 1 | 7 | 3.82 |
| Simone Dantas | 2 | 119 | 24.99 |
| Dieter Rautenbach | 3 | 946 | 138.87 |