Journal article icon

Journal article

For most graphs H, most H-free graphs have a linear homogeneous set

Abstract:
Erdos and Hajnal conjectured that for every graph H there is a constant ε =ε (H) > 0 such that every graph G that does not have H as an induced subgraph contains a clique or a stable set of order Ω(|V (G)|ε). The conjecture would be false if we set ε = 1; however, in an asymptotic setting, we obtain this strengthened form of Erdos and Hajnal's conjecture for almost every graph H, and in particular for a large class of graphs H defined by variants of the colouring number.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1002/rsa.20488

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Statistics
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Role:
Author
Publisher:
Wiley Online Library Publisher's website
Journal:
Random Structures and Algorithms Journal website
Volume:
45
Issue:
3
Pages:
343-361
Chapter number:
3
Publication date:
2013-03-18
Acceptance date:
2012-11-22
DOI:
EISSN:
1098-2418
ISSN:
1042-9832
URN:
uuid:af2b48c7-853d-4538-bb5e-908acaf9d742
Source identifiers:
365262
Local pid:
pubs:365262
Paper number:
3

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP