2022/11/04 by Zhao, Qinghong, Wei, Bing
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.02338
For two given graphs F and H, the Ramsey number R(F,H) is the smallest integer N such that any red-blue edge-coloring of the complete graph KN contains a red F or a blue H. When F=H, we simply write R2(H). For an positive integer n, let K1,n be a star with n+1 vertices, Fn be a fan with 2n+1 vertices consisting of n triangles sharing one common vertex, and nK3 be a graph with 3n vertices obtained from the disjoint union of n triangles. In 1975, Burr, Erdős and Spencer \citeB proved that R2(nK3)=5n for n≥2. However, determining the exact value of R2(Fn) is notoriously difficult. So far, only R2(F2)=9 has been proved. Notice that both Fn and nK3 contain n triangles and |V(Fn)|<|V(nK3)| for all n≥ 2. Chen, Yu and Zhao (2021) speculated that R2(Fn)≤ R2(nK3)=5n for n sufficiently large. In this paper, we first prove that R(K1,n,Fn)=3n-ε for n≥1, where ε=0 if n is odd and ε=1 if n is even. Applying the exact values of R(K1,n,Fn), we will confirm R2(Fn)≤ 5n for n=3 by showing that R2(F3)=14.