共 50 条
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
相关论文