2025/05/30 by Fan, Xinyue, Hajebi, Sahab, Hajebi, Sepehr +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2505.24100
For graphs G and H, we say that G is H-free if no induced subgraph of G is isomorphic to H, and that G is H-induced-saturated if G is H-free but removing or adding any edge in G creates an induced copy of H. A full characterization of graphs H for which H-induced-saturated graphs exist remains elusive. Even the case where H is a path -- now settled by the collective results of Martin and Smith, Bonamy et al., and Dvoŕǎk -- was already quite challenging. What if H is a cycle? The complete answer for odd cycles was given by Behren et al., leaving the case of even cycles (except for the 4-cycle) wide open. Our main result is the first step toward closing this gap: We prove that for every even cycle H, there is a graph G with at least one edge such that G is H-free but removing any edge from G creates an induced copy of H (in fact, we construct H-induced-saturated graphs for every even cycle H on at most 10 vertices).