Ramsey-type theorems with forbidden subgraphs

被引:64
|
作者
Alon, N [1 ]
Pach, J
Solymosi, J
机构
[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel
[2] Hungarian Acad Sci, Inst Comp & Automat, H-1518 Budapest, Hungary
[3] Hungarian Acad Sci, Inst Math, H-1364 Budapest, Hungary
关键词
AMS Subject Classification (2000) Classes:  05D10, 05D40, 05C20;
D O I
10.1007/s004930100016
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdos and Hajnal. Is it true that for every graph H, there exists an epsilon (H) > 0 such that ally H-free graph with n vertices contains either a complete or an empty subgraph of size at least n(epsilon (H))? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments. In order to prove the equivalence, we establish several Ramsey type results for tournaments.
引用
收藏
页码:155 / 170
页数:16
相关论文
共 50 条
  • [31] Minimal vertex Ramsey graphs and minimal forbidden subgraphs
    Borowiecka-Olszewska, M
    Drgas-Burchardt, E
    Mihók, P
    DISCRETE MATHEMATICS, 2004, 286 (1-2) : 31 - 36
  • [32] A Ramsey-type problem and the Turan numbers
    Alon, N
    Erdos, P
    Gunderson, DS
    Molloy, M
    JOURNAL OF GRAPH THEORY, 2002, 40 (02) : 120 - 129
  • [33] Ramsey-type constructions for arrangements of segments
    Kyncl, Jan
    EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (03) : 336 - 339
  • [34] RAMSEY-TYPE PROBLEM FOR PATHS IN DIGRAPHS
    WILLIAMSON, JE
    MATHEMATISCHE ANNALEN, 1973, 203 (02) : 117 - 118
  • [35] Ramsey-type theorem for spatial graphs
    Negami, S
    GRAPHS AND COMBINATORICS, 1998, 14 (01) : 75 - 80
  • [36] On a Ramsey-type problem of Erds and Pach
    Kang, Ross J.
    Long, Eoin
    Patel, Viresh
    Regts, Guus
    BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2017, 49 (06) : 991 - 999
  • [37] Ramsey-type results for oriented trees
    Kohayakawa, Y
    Luczak, T
    Rodl, V
    JOURNAL OF GRAPH THEORY, 1996, 22 (01) : 1 - 8
  • [38] Constructive bounds for a Ramsey-type problem
    Alon, N
    Krivelevich, M
    GRAPHS AND COMBINATORICS, 1997, 13 (03) : 217 - 225
  • [39] A RAMSEY-TYPE THEOREM FOR TRACEABLE GRAPHS
    GALVIN, F
    RIVAL, I
    SANDS, B
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1982, 33 (01) : 7 - 16
  • [40] A generalization of a Ramsey-type theorem on hypermatchings
    Baginski, P
    JOURNAL OF GRAPH THEORY, 2005, 50 (02) : 142 - 149