Infinitely many minimally non-Ramsey size-linear graphs
A graph G is said to be Ramsey size-linear if r ( G , H ) = O G ( e ( H ) ) for every graph H with no isolated vertices. Erdős, Faudree, Rousseau, and Schelp observed that K 4 is not Ramsey size-linear, but each of its proper subgraphs is, and they asked whether there exist infinitely many such graphs. In this short note, we answer this question in the affirmative.
Authors
- Yuval Wigderson (ORCID: https://orcid.org/0000-0001-5909-9250)
Publication Details
- Journal
- European Journal of Combinatorics
- Published
- 2025-05-10
- DOI
- https://doi.org/10.1016/j.ejc.2025.104175
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00