2024/04/16 by Cameron, Kathie, Chaniotis, Aristotelis, de Figueiredo, Celina M. H. +1 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2404.10888
For a property P of graphs, the P-Sandwich-Problem, introduced by Golumbic and Shamir (1993), is the following: Given a pair of graphs (G1, G2) on the same vertex set V, does there exist a graph G such that V(G)=V, E(G1)⊆ E(G) ⊆ E(G2), and G satisfies 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 C and a graph G we say that G is \em C-free if it contains no induced subgraph isomorphic to a member of C. In this paper we prove that if P is the property of being odd-hole-free or the property of being even-hole-free, then the P-Sandwich-Problem is NP-hard.