The Erdös-Hajnal conjecture - A survey

Research output: Contribution to journalArticlepeer-review

64 Scopus citations


The Erdös-Hajnal conjecture states that for every graph H, there exists a constant δ(H)>0 such that every graph G with no induced subgraph isomorphic to H has either a clique or a stable set of size at least |V(G)|δ(H). This article is a survey of some of the known results on this conjecture.

Original languageEnglish (US)
Pages (from-to)178-190
Number of pages13
JournalJournal of Graph Theory
Issue number2
StatePublished - Feb 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


  • Erdös-Hajnal conjecture
  • induced subgraphs


Dive into the research topics of 'The Erdös-Hajnal conjecture - A survey'. Together they form a unique fingerprint.

Cite this