تقرير
The sandwich problem for odd-hole-free and even-hole-free graphs
| العنوان: | The sandwich problem for odd-hole-free and even-hole-free graphs |
|---|---|
| المؤلفون: | Cameron, Kathie, Chaniotis, Aristotelis, de Figueiredo, Celina M. H., Spirkl, Sophie |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics |
| الوصف: | 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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2404.10888 |
| رقم الأكسشن: | edsarx.2404.10888 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |