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 条
  • [1] Ramsey-type Theorems with Forbidden Subgraphs
    Noga Alon
    János Pach
    József Solymosi
    Combinatorica, 2001, 21 : 155 - 170
  • [2] Colouring of graphs with Ramsey-type forbidden subgraphs
    Dabrowski, Konrad K.
    Golovach, Petr A.
    Paulusma, Daniel
    THEORETICAL COMPUTER SCIENCE, 2014, 522 : 34 - 43
  • [3] Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
    Dabrowski, Konrad K.
    Golovach, Petr A.
    Paulusma, Daniel
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2013, 2013, 8165 : 201 - 212
  • [4] RAMSEY-TYPE THEOREMS
    ERDOS, P
    HAJNAL, A
    DISCRETE APPLIED MATHEMATICS, 1989, 25 (1-2) : 37 - 52
  • [5] SOME RAMSEY-TYPE THEOREMS
    ERDOS, P
    GALVIN, F
    DISCRETE MATHEMATICS, 1991, 87 (03) : 261 - 269
  • [6] Induced Ramsey-type theorems
    Fox, Jacob
    Sudakov, Benny
    ADVANCES IN MATHEMATICS, 2008, 219 (06) : 1771 - 1800
  • [7] Turan- and Ramsey-type results for unavoidable subgraphs
    Muyesser, Alp
    Tait, Michael
    JOURNAL OF GRAPH THEORY, 2022, 101 (04) : 597 - 622
  • [8] Using Ultrafilters to Prove Ramsey-type Theorems
    Fernandez-Breton, David J.
    AMERICAN MATHEMATICAL MONTHLY, 2022, 129 (02): : 116 - 132
  • [9] Generalizations of some Ramsey-type theorems for matchings
    Bialostocki, A
    Voxman, W
    DISCRETE MATHEMATICS, 2001, 239 (1-3) : 101 - 107
  • [10] A RAMSEY-TYPE THEOREM FOR MULTIPLE DISJOINT COPIES OF INDUCED SUBGRAPHS
    Nakamigawa, Tomoki
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (02) : 249 - 261