The Erdös-Hajnal conjecture - A survey

Research output: Contribution to journalArticle

35 Scopus citations

Abstract

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
Volume75
Issue number2
DOIs
StatePublished - Feb 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Erdös-Hajnal conjecture
  • induced subgraphs

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

  • Cite this