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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom