Ramsey numbers of bounded degree trees versus general graphs

Abstract

For every $k\ge 2$ and $\Delta$, we prove that there exists a constant $C_{\Delta ,k}$ such that the following holds. For every graph $H$ with $\chi (H)=k$ and every tree with at least $C_{\Delta ,k}|H|$ vertices and maximum degree at most $\Delta$, the Ramsey number $R(T,H)$ is $(k-1)(|T|-1)+\sigma (H)$, where $\sigma (H)$ is the size of a smallest colour class across all proper $k$-colourings of $H$. This is tight up to the value of $C_{\Delta ,k}$, and confirms a conjecture of Balla, Pokrovskiy, and Sudakov.

Cited by in corpus (1)

• Spanning clique subdivisions in pseudorandom graphs