Premium
The Erdös–Hajnal Conjecture—A Survey
Author(s) -
Chudnovsky Maria
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21730
Subject(s) - combinatorics , conjecture , mathematics , clique , graph , induced subgraph , discrete mathematics , vertex (graph theory)
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.