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

author:

Fan, Chunchao (Fan, Chunchao.) [1] | Huang, Junqiang (Huang, Junqiang.) [2] | Lin, Qizhong (Lin, Qizhong.) [3] (Scholars:林启忠)

Indexed by:

Scopus SCIE

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:

Book Complete multipartite graph Ramsey number

Community:

  • [ 1 ] [Fan, Chunchao]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China
  • [ 2 ] [Huang, Junqiang]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China
  • [ 3 ] [Lin, Qizhong]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China

Reprint 's Address:

  • 黄俊强

    [Huang, Junqiang]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China

Show more details

Version:

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

Online/Total:51/10135036
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