• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Fan, C. (Fan, C..) [1] | Huang, J. (Huang, J..) [2] | Lin, Q. (Lin, Q..) [3]

Indexed by:

Scopus

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:

Book Complete multipartite graph Ramsey number

Community:

  • [ 1 ] [Fan C.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, 350108, China
  • [ 2 ] [Huang J.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, 350108, China
  • [ 3 ] [Lin Q.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, 350108, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Graphs and Combinatorics

ISSN: 0911-0119

Year: 2024

Issue: 6

Volume: 40

0 . 6 0 0

JCR@2023

Cited Count:

WoS CC 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:

Online/Total:69/10135938
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1