Infinite family with no finite induced-saturated graphs
Problem 21 · arXiv:2506.08810
Status open high confidence
Problem 21 asks whether there exists an infinite family of finite graphs (containing no cliques or independent sets) each of which admits no finite induced-saturated graph. The only known example of a graph H (not a clique or independent set) for which no finite H-induced-saturated graph exists is P_4; beyond P_4, no further such graph H has been identified. No follow-up work addressing the existence of an infinite such family was found in indexed literature as of May 2026.
Reviewer notes. The source paper was published in the Canadian Journal of Mathematics in March 2026 (DOI: 10.4153/S0008414X26102132), confirming it as a peer-reviewed result. Problem 21 is a very recent open question; wide web search spanning arXiv and journal databases found no follow-up. The problem is closely related to the known anomaly of P_4 (and paths P_t with t=1,4) having no finite induced-saturated graph, while the paper proves countably infinite H-induced-saturated graphs exist for all finite H not a clique or independent set.
Context
The paper establishes that every finite graph $H$ that is not a clique or independent set admits a countably infinite $H$-induced-saturated graph. In the finite setting the picture is far less clear: beyond $P_4$, cliques, and independent sets, no other finite graph $H$ is known to lack a finite $H$-induced-saturated graph, so it is open whether infinitely many such exceptions exist.
Source paper
Infinite induced-saturated graphs
Marthe Bonamy, Carla Groenland, Tom Johnston, Natasha Morrison, Alex Scott · 2025-09-01
https://arxiv.org/abs/2506.08810