Almost All F-Free Graphs Have The Erdos-Hajnal Property

Abstract : Erdős and Hajnal conjectured that, for every graph H, there exists a constant ɛ(H) > 0 such that every H-free graph G (that is, not containing H as an induced subgraph) must contain a clique or an independent set of size at least |G|ɛ( H). We prove that there exists ɛ(H) such that almost every H-ïvee graph G has this property, meaning that, amongst the if-free graphs with n vertices, the proportion having the property tends to one as n → ∞.
Type de document :
Chapitre d'ouvrage
An Irregular Mind, 21, pp.405-414, 2010, 〈10.1007/978-3-642-14444-8_11〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00806800
Contributeur : Alexandre Pinlou <>
Soumis le : mardi 2 avril 2013 - 13:35:02
Dernière modification le : mercredi 26 septembre 2018 - 21:52:01

Lien texte intégral

Identifiants

Citation

Martin Loebl, Bruce Reed, Alex Scott, Andrew Thomason, Stéphan Thomassé. Almost All F-Free Graphs Have The Erdos-Hajnal Property. An Irregular Mind, 21, pp.405-414, 2010, 〈10.1007/978-3-642-14444-8_11〉. 〈lirmm-00806800〉

Partager

Métriques

Consultations de la notice

292