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.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Erdös-Hajnal conjecture
- induced subgraphs