paper

On Ramsey size-linear graphs and related questions

arXiv:2202.10388

Abstract

In this paper we prove several results on Ramsey numbers $R (H, F)$ for a fixed graph $H$ and a large graph $F$ , in particular for $F = K_{n}$ . These results extend earlier work of ErdÅs, Faudree, Rousseau and Schelp and of Balister, Schelp and Simonovits on so-called Ramsey size-linear graphs. Among others, we show that if $H$ is a subdivision of $K_{4}$ with at least $6$ vertices, then $R (H, F) = O (v (F) + e (F))$ for every graph $F$ . We also conjecture that if $H$ is a connected graph with $e (H) - v (H) \leq (2 k + 1) - 2$ , then $R (H, K_{n}) = O (n^{k})$ . The case $k = 2$ was proved by ErdÅs, Faudree, Rousseau and Schelp. We prove the case $k = 3$ .