Journal article
Infinite induced-saturated graphs
- 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 𝑃4, 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 1.1MB, Terms of use)
-
- Publisher copy:
- 10.4153/S0008414X26102132
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Grant:
- EP/X013642/1
- Publisher:
- Cambridge University Press
- Journal:
- Canadian Journal of Mathematics More from this journal
- Publication date:
- 2026-03-24
- Acceptance date:
- 2026-02-24
- DOI:
- EISSN:
-
1496-4279
- ISSN:
-
0008-414X
- Language:
-
English
- Keywords:
- Pubs id:
-
2381245
- Local pid:
-
pubs:2381245
- Deposit date:
-
2026-02-24
- ARK identifier:
Terms of use
- Copyright holder:
- Bonamy et al.
- Copyright date:
- 2026
- Rights statement:
- © The Author(s), 2026. Published by Cambridge University Press on behalf of Canadian Mathematical Society. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record