Ramsey goodness and beyond

被引：38

作者：

Nikiforov, Vladimir ^{[1
]}

Rousseau, Cecil C. ^{[1
]}

机构：

[1] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA

来源：

COMBINATORICA | 2009年 / 29卷 / 02期

关键词：

NUMBERS INVOLVING GRAPHS;

D O I：

10.1007/s00493-009-2409-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In a seminal paper from 1983, Burr and ErdAs started the systematic study of Ramsey numbers of cliques vs. large sparse graphs, raising a number of problems. In this paper we develop a new approach to such Ramsey problems using a mix of the Szemer,di regularity lemma, embedding of sparse graphs, Turan type stability, and other structural results. We give exact Ramsey numbers for various classes of graphs, solving five - all but one - of the Burr-ErdAs problems.

引用

页码：227 / 262

页数：36

共 32 条

[1]

Andrasfai B., 1974, Discrete Mathematics, V8, P205, DOI 10.1016/0012-365X(74)90133-2

[2]

[Anonymous], 1998, GRAD TEXT M

[3] Joints in graphs [J].

Bollobas, Bela ;

Nikiforova, Vladimir .

DISCRETE MATHEMATICS, 2008, 308 (01) :9-19

[4]

BRANDT S., 1996, EXPANDING GRAPHS RAM

[5] GENERALIZATIONS OF A RAMSEY-THEORETIC RESULT OF CHVATAL [J].

BURR, SA ;

ERDOS, P .

JOURNAL OF GRAPH THEORY, 1983, 7 (01) :39-51

[6] ON RAMSEY NUMBERS INVOLVING STARLIKE MULTI-PARTITE GRAPHS [J].

BURR, SA ;

FAUDREE, RJ ;

ROUSSEAU, CC ;

SCHELP, RH .

JOURNAL OF GRAPH THEORY, 1983, 7 (04) :395-409

[7] GOODNESS OF TREES FOR GENERALIZED BOOKS [J].

BURR, SA ;

ERDOS, P ;

FAUDREE, RJ ;

ROUSSEAU, CC ;

SCHELP, RH ;

GOULD, RJ ;

JACOBSON, MS .

GRAPHS AND COMBINATORICS, 1987, 3 (01) :1-6

[8]

BURR SA, 1981, J LOND MATH SOC, V24, P405

[9] WHAT CAN WE HOPE TO ACCOMPLISH IN GENERALIZED RAMSEY THEORY [J].

BURR, SA .

DISCRETE MATHEMATICS, 1987, 67 (03) :215-225

[10] MULTICOLOR RAMSEY NUMBERS INVOLVING GRAPHS WITH LONG SUSPENDED PATHS [J].

BURR, SA .

DISCRETE MATHEMATICS, 1982, 40 (01) :11-20

← 1 2 3 4 →