Indexed by:
Abstract:
For graphs H1 and H2, the Ramsey number r(H1,H2) is the smallest positive integer N such that any graph G on N vertices contains H1 as a subgraph, or its complement contains H2 as a subgraph. Let Bn(k) denote the book graph on n+k vertices which consists of n copies of Kk+1 all sharing a common Kk, and let H:=Kp(a1,⋯,ap) be the complete p-partite graph with parts of sizes a1,⋯,ap. Recently, strengthening a result of Fox, He and Wigderson (Adv. Combin. 4 (2023), 21pp), Fan and Lin (J. Combin. Theory Ser. A 199 (2023), 19pp) showed that for every k,p,t≥2, there exists δ>0 such that the following holds for all large n. Let 1≤a1≤⋯≤ap-1≤t and ap≤δn be positive integers. If a1=1, then r(H,Bn(k))≤(p-1)(n+ka2-1)+1. The inequality is tight if n≡1(moda2). In this paper, we improve the above upper bounds for the cases when n≡2(moda2) and n≡3(moda2). Combining the new upper bounds and constructions of the lower bounds for these cases, we are able to determine the exact values of r(Kp(a1,⋯,ap),Bn(k)) when p=3. The bound on 1/δ we obtain is not of tower-type since our proof does not rely on the regularity lemma. © The Author(s), under exclusive licence to Springer Nature Japan KK 2024.
Keyword:
Reprint 's Address:
Email:
Source :
Graphs and Combinatorics
ISSN: 0911-0119
Year: 2024
Issue: 6
Volume: 40
0 . 6 0 0
JCR@2023
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: