Ramsey numbers of sparse graphs versus disjoint books

Abstract

Let $B_k$ denote a book on $k+2$ vertices and $t{B}_k$ be $t$ vertex-disjoint $B_k$'s. For any integers $k\ge 2$ and $t\ge 1$, there exists a positive constant $\epsilon =\epsilon (k,t)$ such that every connected graph $G$ with $n\ge 111t^3{k}^3$ vertices and at most $n(1+\epsilon )$ edges satisfies $$r(G,t{B}_k)=2n+t-2.$$ Our result extends the work of Erdős, Faudree, Rousseau, and Schelp (1988), who established the corresponding result for $G$ being a tree and $t=1$.

arXiv comment20 pages