Indexed by:
Abstract:
For graphs H (1) and H (2) , the Ramsey number r(H-1, H (2) ) is the smallest positive integer N such that any graph G on N vertices contains H (1) as a subgraph, or its complement contains H (2) as a subgraph. Let B ((k)) (n) denote the book graph on n + k vertices which consists of n copies of K (k +1) all sharing a common K (k) , and let H := K-p(a(1), ..., a(p)) be the complete p-partite graph with parts of sizes a 1 ,... , a p . 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 delta > 0 such that the following holds for all large n . Let 1 <= a (1) <= center dot center dot center dot <= a (p -1) <= t and a(p) <= delta n be positive integers. If a (1) = 1, then r(H, B ((k)) (n) ) <= (p - 1 )( n + ka (2) - 1 ) + 1. The inequality is tight if n equivalent to 1 ( mod a 2 ) . In this paper, we improve the above upper bounds for the cases when n equivalent to 2 ( mod a 2 ) and n equivalent to 3 ( mod a (2) ) . Combining the new upper bounds and constructions of the lower bounds for these cases, we are able to determine the exact values of r ( K (p) ( a (1) ,... ,a(p)), B (n) ((k)) ) when p = 3. The bound on 1/delta we obtain is not of tower-type since our proof does not rely on the regularity lemma.
Keyword:
Reprint 's Address:
Version:
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