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 条
  • [41] Constructive Bounds for a Ramsey-Type Problem
    Noga Alon
    Michael Krivelevich
    Graphs and Combinatorics, 1997, 13 : 217 - 225
  • [42] Ramsey-Type Results for Gallai Colorings
    Gyarfas, Andras
    Sarkozy, Gabor N.
    Sebo, Andras
    Selkow, Stanley
    JOURNAL OF GRAPH THEORY, 2010, 64 (03) : 233 - 243
  • [43] RAMSEY-TYPE PROPERTIES OF RELATIONAL STRUCTURES
    ELZAHAR, M
    SAUER, NW
    DISCRETE MATHEMATICS, 1991, 94 (01) : 1 - 10
  • [44] NOTE ON A RAMSEY-TYPE PROBLEM IN GEOMETRY
    CSIZMADIA, G
    TOTH, G
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 1994, 65 (02) : 302 - 306
  • [45] Attosecond optical and Ramsey-type interference
    Matsubara, Takuya
    Nabekawa, Yasuo
    Ishikawa, Kenichi L.
    Yamanouchi, Kaoru
    Midorikawa, Katsumi
    2021 CONFERENCE ON LASERS AND ELECTRO-OPTICS EUROPE & EUROPEAN QUANTUM ELECTRONICS CONFERENCE (CLEO/EUROPE-EQEC), 2021,
  • [46] Ramsey-Type Theorem for Spatial Graphs
    Seiya Negami
    Graphs and Combinatorics, 1998, 14 : 75 - 80
  • [47] A note on a Ramsey-type problem for sequences
    Dudek, Andrzej
    ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (03):
  • [48] A new lower, bound for a Ramsey-type problem
    Sudakov, B
    COMBINATORICA, 2005, 25 (04) : 487 - 498
  • [50] Ramsey-Type Results for Unions of Comparability Graphs
    Adrian Dumitrescu
    Géza Tóth
    Graphs and Combinatorics, 2002, 18 : 245 - 251