Abstract
A graph G is H-induced-saturated if G is H-free but deleting any edge or adding any edge creates an induced copy of H. There are nontrivial graphs H, such as , for which no finite H-induced-saturated graph G exists. We show that for every finite graph H that is not a clique or an independent set, there always exists a countable H-induced-saturated graph. In fact, we show that a far stronger property can be achieved: there is a countably infinite H-free graph G such that any graph obtained by making a locally finite set of changes to G contains a copy of H.
| Original language | English |
|---|---|
| Number of pages | 31 |
| Journal | Canadian Journal of Mathematics |
| Early online date | 24 Mar 2026 |
| DOIs | |
| Publication status | E-pub ahead of print - 24 Mar 2026 |
Bibliographical note
© The Author(s), 2026.Keywords
- induced subgraph
- 05C75
- hereditary graph class
- Infinite graphs
- induced saturation
- 05C63
Fingerprint
Dive into the research topics of 'Infinite induced-saturated graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver