Infinitely many minimally Ramsey size-linear graphs

Yuval Wigderson

Published 2024-09-09Version 1

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\H{o}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.