Skip to main navigation Skip to search Skip to main content

Infinite induced-saturated graphs

Marthe Bonamy, Carla Groenland*, Tom Johnston, Natasha Morrison, Alexander Scott

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

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 languageEnglish
Number of pages31
JournalCanadian Journal of Mathematics
Early online date24 Mar 2026
DOIs
Publication statusE-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