Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2505.24100 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913869556875264 |
|---|---|
| author | Fan, Xinyue Hajebi, Sahab Hajebi, Sepehr Spirkl, Sophie |
| author_facet | Fan, Xinyue Hajebi, Sahab Hajebi, Sepehr Spirkl, Sophie |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24100 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Halfway to induced saturation for even cycles Fan, Xinyue Hajebi, Sahab Hajebi, Sepehr Spirkl, Sophie Combinatorics 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). |
| title | Halfway to induced saturation for even cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.24100 |