Infinitely many minimally non-Ramsey size-linear graphs

Abstract

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.

arXiv comment2 pages