Ramsey-type theorems with forbidden subgraphs

Citation
N. Alon et al., Ramsey-type theorems with forbidden subgraphs, COMBINATORI, 21(2), 2001, pp. 155-170
Citations number
16
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
21
Issue
2
Year of publication
2001
Pages
155 - 170
Database
ISI
SICI code
0209-9683(2001)21:2<155:RTWFS>2.0.ZU;2-U
Abstract
A graph is called H-free if it contains no induced copy of H. We discuss th e 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 cl ass of graphs, and give an equivalent reformulation for tournaments. In ord er to prove the equivalence, we establish several Ramsey type results for t ournaments.