Ramsey-type Theorems with Forbidden Subgraphs | Zendy

Noga Alon | Zendy; J x E nos Pach | Zendy; József Solymosi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Ramsey-type Theorems with Forbidden Subgraphs

Author(s) -

Noga Alon,

J x E nos Pach,

József Solymosi

Publication year - 2001

Publication title -

combinatorica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.106

H-Index - 58

eISSN - 1439-6912

pISSN - 0209-9683

DOI - 10.1007/s004930100016

Subject(s) - mathematics , combinatorics , induced subgraph , graph , discrete mathematics , ramsey's theorem , vertex (graph theory)

Dedicated to the memory of Paul Erdős A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research