# The Erdös--Hajnal Conjecture for Long Holes and Antiholes

2 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : Erdös and Hajnal conjectured that for every graph $H$, there exists a constant $c_H$ such that every graph $G$ on $n$ vertices which does not contain an induced copy of $H$ has a clique or a stable set of size $n^{c_H}$. We prove that for every $k$ there exists $c_k>0$ such that every graph $G$ on $n$ vertices not inducing a cycle of length at least $k$ nor its complement contains a clique or a stable set of size at least $n^{c_k}$.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (2), pp.1159-1164. 〈10.1137/140981745〉
Domaine :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01347304
Contributeur : Isabelle Gouat <>
Soumis le : mercredi 20 juillet 2016 - 17:22:02
Dernière modification le : jeudi 31 mai 2018 - 14:54:02

### Citation

Marthe Bonamy, Nicolas Bousquet, Stéphan Thomassé. The Erdös--Hajnal Conjecture for Long Holes and Antiholes. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (2), pp.1159-1164. 〈10.1137/140981745〉. 〈lirmm-01347304〉

### Métriques

Consultations de la notice