2015/11/23 by Brennan, Matthew · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1511.07306
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 G contains K as a subgraph. Let Tn be a tree with n vertices and Fm 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 ≥ 9 that R(Tn, Fm) = 2n - 1 for all n ≥ m2 - m + 1. Zhang, Broersma and Chen showed that R(Sn, Fm) ≥ 2n for n ≤ m2 -m where Sn 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 UCn, which are connected graphs with n vertices and a single cycle. We prove that R(UCn, Fm) = 2n - 1 for all n ≥ m2 - m + 1 where m ≥ 18. In proving this conjecture and extension, we present several methods for embedding trees in graphs, which may be of independent interest.