The sandwich problem for odd-hole-free and even-hole-free graphs
<|reference_start|>The sandwich problem for odd-hole-free and even-hole-free graphs: For a property $\mathcal{P}$ of graphs, the $\mathcal{P}$-\textsc{Sandwich-Problem}, introduced by Golumbic and Shamir (1993), is the following: Given a pair of graphs $(G_1, G_2)$ on the same vertex set $V$, does there exist a graph $G$ such that $V(G)=V$, $E(G_{1})\subseteq E(G) \subseteq E(G_{2})$, and $G$ satisfies $\mathcal{P}$? A {\em hole} in a graph is an induced subgraph which is a cycle of length at least four. An odd (respectively even) hole is a hole of odd (respectively even) length. Given a class of graphs $\mathcal{C}$ and a graph $G$ we say that $G$ is {\em $\mathcal{C}$-free} if it contains no induced subgraph isomorphic to a member of $\mathcal{C}$. In this paper we prove that if $\mathcal{P}$ is the property of being odd-hole-free or the property of being even-hole-free, then the $\mathcal{P}$-\textsc{Sandwich-Problem} is NP-hard.<|reference_end|>
@article{cameron2024the,
    title={The sandwich problem for odd-hole-free and even-hole-free graphs},
    author={Kathie Cameron, Aristotelis Chaniotis, Celina M. H. de Figueiredo,
  Sophie Spirkl},
    journal={arXiv preprint arXiv:2404.10888},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.10888},
    primaryClass={math.CO cs.DM}
}