The Erdös-Hajnal conjecture - A survey

Maria Chudnovsky

doi:10.1002/jgt.21730

The Erdös-Hajnal conjecture - A survey

Maria Chudnovsky

Research output: Contribution to journal › Article › peer-review

67 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 language	English (US)
Pages (from-to)	178-190
Number of pages	13
Journal	Journal of Graph Theory
Volume	75
Issue number	2
DOIs	https://doi.org/10.1002/jgt.21730
State	Published - Feb 2014
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Erdös-Hajnal conjecture
induced subgraphs

Access to Document

10.1002/jgt.21730

Cite this

@article{5d4039f821ba43568325eb4df809dc9e,

title = "The Erd{\"o}s-Hajnal conjecture - A survey",

abstract = "The Erd{\"o}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.",

keywords = "Erd{\"o}s-Hajnal conjecture, induced subgraphs",

author = "Maria Chudnovsky",

year = "2014",

month = feb,

doi = "10.1002/jgt.21730",

language = "English (US)",

volume = "75",

pages = "178--190",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - The Erdös-Hajnal conjecture - A survey

AU - Chudnovsky, Maria

PY - 2014/2

Y1 - 2014/2

N2 - 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.

AB - 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.

KW - Erdös-Hajnal conjecture

KW - induced subgraphs

UR - http://www.scopus.com/inward/record.url?scp=84889666048&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84889666048&partnerID=8YFLogxK

U2 - 10.1002/jgt.21730

DO - 10.1002/jgt.21730

M3 - Article

AN - SCOPUS:84889666048

SN - 0364-9024

VL - 75

SP - 178

EP - 190

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

The Erdös-Hajnal conjecture - A survey

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this