On size Ramsey numbers of graphs with bounded degree

被引：48

作者：

Rödl, V ^{[1
]}

Szemerédi, E

机构：

[1] Emory Univ, Atlanta, GA 30322 USA

[2] Rutgers State Univ, Piscataway, NJ 08854 USA

来源：

COMBINATORICA | 2000年 / 20卷 / 02期

基金：

美国国家科学基金会;

关键词：

Positive Constant; Maximum Degree; Bound Degree; Ramsey Number;

D O I：

10.1007/s004930070024

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Answering a question of J. Beck [2], we prove that there exists a graph G on n vertices with maximum degree three and the size Ramsey number (r) over cap(G) greater than or equal to cn(logn)(alpha) where alpha and c are positive constants.

引用

页码：257 / 262

页数：6

共 6 条

[1] ON SIZE RAMSEY NUMBER OF PATHS, TREES, AND CIRCUITS .1. [J].

BECK, J .

JOURNAL OF GRAPH THEORY, 1983, 7 (01) :115-129

[2]

BECK J, 1990, MATH RAMSEY THEORY, V2, P34

[3]

Erdos P., 1978, Periodica Mathematica Hungarica, V9, P145, DOI 10.1007/BF02018930

[4] ON THE COMBINATORIAL PROBLEMS WHICH I WOULD MOST LIKE TO SEE SOLVED [J].

ERDOS, P .

COMBINATORICA, 1981, 1 (01) :25-42

[5]

FRIEDMAN J, 1981, COMBINATORICA, V7, P71

[6]

Haxell P. E., 1995, Combin. Probab. Comput., V4, P217, DOI DOI 10.1017/S0963548300001619

← 1 →