Star-critical Ramsey numbers involving large books

• Published in: Discrete mathematics 2025-02, Vol.348 (2), p.114270, Article 114270
• Main Authors: Chen, Xun, Lin, Qizhong, Niu, Lin
• Format: Article
• Language: English
• Subjects: Ramsey number; Stability-supersaturation lemma; Star-critical Ramsey number
• ISSN: 0012-365X
• DOI: 10.1016/j.disc.2024.114270

For graphs F,G and H, let F→(G,H) signify that any red/blue edge coloring of F contains either a red G or a blue H. The Ramsey number r(G,H) is defined to be the smallest integer r such that Kr→(G,H). Let Bn(k) be the book graph which consists of n copies of Kk+1 all sharing a common Kk, and let G:=Kp+1(a1,a2,...,ap+1) be the complete (p+1)-partite graph with a1=1, a2|(n−1) and ai≤ai+1. In this paper, avoiding the use of Szemerédi's regularity lemma, we show that for any fixed p≥1, k≥2 and sufficiently large n, Kp(n+a2k−1)+1∖K1,n+a2−2→(G,Bn(k)). This implies that the star-critical Ramsey number r⁎(G,Bn(k))=(p−1)(n+a2k−1)+a2(k−1)+1. As a corollary, r⁎(G,Bn(k))=(p−1)(n+k−1)+k for a1=a2=1 and ai≤ai+1. This solves a problem proposed by Hao and Lin (2018) [11] in a stronger form.