2025/06/10 by Marthe Bonamy, Carla Groenland, Bonamy, Marthe +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2506.08810
openalex publication_date 2025/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 non-trivial graphs H, such as P4, 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 G'≠ G obtained by making a locally finite set of changes to G contains a copy of H.