Ramsey numbers of trees and unicyclic graphs versus fans

Abstract

The generalized Ramsey number $R(H,K)$ is the smallest positive integer $n$ such that for any graph $G$ with $n$ vertices either $G$ contains $H$ as a subgraph or its complement $\overline{G}$ contains $K$ as a subgraph. Let $T_n$ be a tree with $n$ vertices and $F_m$ be a fan with $2m+1$ vertices consisting of $m$ triangles sharing a common vertex. We prove a conjecture of Zhang, Broersma and Chen for $m\ge 9$ that $R(T_n,F_m)=2n-1$ for all $n\ge m^2-m+1$. Zhang, Broersma and Chen showed that $R(S_n,F_m)\ge 2n$ for $n\le m^2-m$ where $S_n$ is a star on $n$ vertices, implying that the lower bound we show is in some sense tight. We also extend this result to unicyclic graphs $U{C}_n$, which are connected graphs with $n$ vertices and a single cycle. We prove that $R(U{C}_n,F_m)=2n-1$ for all $n\ge m^2-m+1$ where $m\ge 18$. In proving this conjecture and extension, we present several methods for embedding trees in graphs, which may be of independent interest.

arXiv comment23 pages, updated to match DM version