Ramsey functions involving Km,n with n large

被引:15
作者
Li, YS [1 ]
Tang, XQ
Zang, WN
机构
[1] Tongji Univ, Dept Math, Shanghai 200092, Peoples R China
[2] Hohai Univ, Dept Math, Nanjing 210098, Peoples R China
[3] Governors State Univ, Comp Sci Program, University Pk, IL 60466 USA
[4] Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China
关键词
Ramsey number; bipartite graph; asymptotic formula;
D O I
10.1016/j.disc.2005.01.008
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For fixed integers m, k >= 2, it is shown that the k-color Ramsey number r(k) (K-m, (n)) and the bipartite Ramsey number b(k) (m, n) are both asymptotically equal to k(m)n as n -> infinity, and that for any graph H on m vertices, the two-color Ramsey number r (H + (K-n,) over bar K-n) is at most (1 + o(1))n(m+ 1) /(log n)(m-1). Moreover, the order of magnitude of r (H + (K-n,) over bar K-n) is proved to be n(m+) 1 / (log n)(m) if H not equal K-m as n -> infinity. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:120 / 128
页数:9
相关论文
共 20 条
[1]  
Alon N., 2000, PROBABILISTIC METHOD
[2]  
Bollob┬u├s B., 2013, MODERN GRAPH THEORY, V184
[3]  
Caro Y., 2001, ELECTRON J COMB, V8, pR17
[4]  
Chung F., 1998, Erdos on Graphs: His Legacy of Unsolved Problems
[5]   MULTICOLOR RAMSEY NUMBERS FOR COMPLETE BIPARTITE GRAPHS [J].
CHUNG, FRK ;
GRAHAM, RL .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (02) :164-169
[6]  
CHUNG FRK, 1974, THESIS U PENNSYLVANI
[7]   GENERALIZED RAMSEY THEORY FOR GRAPHS .2. SMALL DIAGONAL NUMBERS [J].
CHVATAL, V ;
HARARY, F .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 32 (02) :389-+
[8]  
Chvatal V., 1977, J. Graph Theory, V1, P93, DOI [10.1002/jgt.3190010118, DOI 10.1002/JGT.3190010118]
[9]  
ERDOS P, 1981, COMBINATORICS GRAPH, P9
[10]  
Exoo G., 1989, GRAPH THEORY COMBINA, P207